LeetCodeOJブラシ問題の15-16【3 Sum(三数と問題)】

9590 ワード

本文は2つの問題である:【3数と(3 Sum)】と【最近の3数と(3 Sum Closest)】問題
第一部分は3 Sum問題を分析し、第二部分は3 Sum Closest問題を分析し、二つの問題の構想が似ているので、ここで一緒に分析する.その中の3 Sum問題はまだコンピュータ科学分野で解決されていない問題の一つのようだが,もちろん,より良い解決策はまだ見つかっていない.
1. 3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

意味は簡単です.つまり、整数配列を与えて、中から3つの数a ,b ,cを探して、a+b+c=0にします.条件を満たすすべての三元グループ解セットを見つけます.また,解セットに重複する解は現れない.

Array

Two Pointers

Solutions

1 3Sum -- 61~69ms

は、まず配列を昇順に並べ替え、次に1つずつ整数を選択し、残りの配列要素から2つの数字を選択して、この3つの数字の和を0にします.

残りの2つの数字を選択すると、2番目の数字は1番目の数字の次の数字から始まります.これは、1番目の数字とそれ以前の数字が検索されたからです.解があれば、きっと見つけたに違いない.2番目の数字は1番目の数字の次の数字から後ろに選択されます.3番目の数字は最後の数字から前に選択されます.配列がソートされているので、存在すれば必ず見つかります.

この考えのコードは以下の通りである:

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > res;
        if(num.size()<3) return res;//    
        sort(num.begin(),num.end()); //   

    int beg , end , sum;
    vector<int> tmp(3,0);
    for(int i = 0;i<num.size()-2;++i){
        //            ，            
        if(num[i]>0)break;
        if((i>0) && num[i]==num[i-1]) continue;
        beg = i + 1;
        end = num.size()-1;
        while(beg < end){
            sum=num[beg] + num[end] + num[i];
            if( sum< 0)        ++beg;
            else if(sum > 0)   --end;
            else{
                tmp[0] = num[i];
                tmp[1] = num[beg];
                tmp[2] = num[end];
                res.push_back(tmp);
                //               ，            
                while(beg<end && num[beg]==tmp[1]) ++beg;
                while(beg<end && num[end]==tmp[2]) --end;
                if(beg>=end) break;
            }
        }
    }
    return res;
}
};

テストセットテストを行った后(ブログ园ここの画像はロードできないようです~):https://github.com/bbxytl/LeetCodesOJ/blob/master/Algorithms/15%203Sum/images/pic1.png

ウィキペディアでは3 Sumについての説明がありますが、同時にStackOverflowを探してみると、現在はこの複雑度$O(N^2)$のソリューションしかなく、もっと良い解決策がない~~~ということに気づき、見つけられなかったのかもしれません.ウィキペディアで述べたアルゴリズムの思想は上の方法であり、偽コードを与えた:

sort(S);
 for i=0 to n-3 do
    a = S[i];
    start = i+1;
    end = n-1;
    while (start < end) do
       b = S[start];
       c = S[end];
       if (a+b+c == 0) then
          output a, b, c;
          // Continue search for all triplet combinations summing to zero.
           start = start + 1
           end = end - 1
       else if (a+b+c > 0) then
          end = end - 1;
       else
          start = start + 1;
       end
    end
 end

また、ウィキペディアで与えられた未解決のコンピュータ科学問題のアルゴリズムによれば、3 SUM問題を二次時間で解決できるかという問題があります.

https://github.com/bbxytl/LeetCodesOJ/blob/master/Algorithms/15%203Sum/images/pic2.png
ふろく

GitHub-LeetCodesOJ

GitHub-Blog

2. 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Array

Two Pointers

Solutions

1 3Sum Closest -- 18ms

この問題の思想は[3 Sum]を求める思想と類似しているので,同思想を用いて解くことができる.

は、まず配列を昇順に並べ替え、次に1つずつ整数を選択し、残りの配列要素から2つの数字を選択し、この3つの数字の和sumを求める.

sumとtargetのサイズを比較し、等しい場合は、3数とtargetに最も近い距離が0であることを示します.この場合は限界であり、これより近いものはあり得ないので、直接このsumに戻ることができます.

sum != targetであれば現在の2つの数の間の距離dt=abs(sum-target)と現在求められている最短距離disのどちらがより小さいかを判断し、dt<disであればtargetに近い解が現れたことを示す.この解の和resを記録します.

サイクルが終了するとresに記録されるのはtargetに最も近い3数和である.

この考えのコードは以下の通りである:

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        int n=num.size();
        if(n<3)return 0;
        sort(num.begin(),num.end());
        int beg,end,sum=0;
        int dis=INT_MAX;
        int res;
        for(int i=0;i<n-2;++i){
            beg=i+1;
            end=n-1;
            while(beg<end){
                sum=num[i]+num[beg]+num[end];
                if(sum==target)return sum;
                else if(sum<target) ++beg;
                else --end;
                int dt=(abs(sum-target));
                if(dis>dt){
                    dis=dt;
                    res=sum;
                }
            }
        }
        return res;
    }
};

試験セット試験後:https://github.com/bbxytl/LeetCodesOJ/blob/master/Algorithms/16%203Sum%20Closest/images/pic1.png

2 3Sum Closest -- 15ms

共有エリアで、

という解法を見つけました.

私たちのさっきの考えは、まず1つの数字を確定して位置決めし、それから残りの2つの数字を遍歴することです.ここの考えはちょうど逆です.まず2つの数字を確定してから、残りの1つを探します.

配列を先にソートし、最初と最後の2つの数を位置決めします.次に、新しいターゲット数newTarget = target - (num[start]+num[end])を求め、残りの数値を2点で検索します.使用する二分検索で返される数値は、比較的条件に合致する配列の数値の下付き記号です.

二分法の時間的複雑さは$O(logn)$

である.

検出された数字に基づいて、3数とcurSumを求め、最終的に要求されたtargetとの距離が最小距離mindiffより小さいかどうかを比較し、小さい場合は、最小距離mindiffに再付与するより小さな解を見つけることを示す.次の検索に進みます.

以上の解析から,このアルゴリズムの時間的複雑さは$O(Nlogn)$であることが分かった.方法1の$O(N^2)$よりも優れている.

次は私が改善したコードです:

class Solution {
    //     
    int findTarget(vector<int> &num, int start, int end, int target) {
        if (start==end) return start;
        if (end-start==1)
            return abs(num[end]-target) > abs(num[start]-target) 
                    ? start : end;
        int mid = (start+end)/2;
        if (num[mid]==target)    return mid;
        else if(num[mid]>target) 
            return findTarget(num, start, mid, target);
        else return findTarget(num, mid, end, target);
    }
public:
    int threeSumClosest(vector<int> &num, int target) {
        int res=0;
        if(num.size()<=3){
            for(auto v : num) res+=v;
            return res;
        }
        sort(num.begin(), num.end());
        int start = 0;
        int end = int(num.size()-1);
        int mindiff = INT_MAX;
        while (start<end-1) {
            int newTarget = target - (num[start] + num[end]);
            int p = findTarget(num, start+1, end-1, newTarget);
            int curSum = num[start] + num[end] + num[p];
            if (curSum == target) {
                return target;
            }else if(curSum > target) end--;
                    else start++;
            mindiff = abs(mindiff)>abs(target-curSum) ? target-curSum : mindiff;
        }
        res=target-mindiff;
        return res;
    }
};

試験セット試験後:https://github.com/bbxytl/LeetCodesOJ/blob/master/Algorithms/16%203Sum%20Closest/images/pic2.png

ふろく

GitHub-LeetCodesOJ

GitHub-Blog

mybatis-plus idプライマリキー生成ピット

pytorchを解決するRuntimeError:CUDA out of memory.そしてlossが超大きな原因になった