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).

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

  • Solutions
  • 1 3Sum Closest -- 18ms
  • この問題の思想は[3 Sum]を求める思想と類似しているので,同思想を用いて解くことができる.
  • は、まず配列を昇順に並べ替え、次に1つずつ整数を選択し、残りの配列要素から2つの数字を選択し、この3つの数字の和sumを求める.
  • 残りの2つの数字を選択すると、2番目の数字は1番目の数字の次の数字から始まります.これは、1番目の数字とそれ以前の数字が検索されたからです.解があれば、きっと見つけたに違いない.2番目の数字は1番目の数字の次の数字から後ろに選択されます.3番目の数字は最後の数字から前に選択されます.配列がソートされているので、存在すれば必ず見つかります.
  • 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