LeetCodeの15.三数の和(3 Sum)まとめ

生命は止まらない、ブラシの問題は止まらない~~~~~
先日からずっとやっていました.三数の和、この問題はLeetCodeとLeetCodeの中国で多くの称賛を得て、絶対的な良い問題です!しかし、私がこの問題が好きなのは、急速なソートの思想を採用しているからだけです.
構想を整理してからコードの実現まで、重いBugsの大関を突破して、ついに提出に成功して、白さんにとって、本当に容易ではありません.次に、この問題の解題の構想を共有して、C++、java、pythonのコードで実現して、みんなに助けを提供することを望んでいます.
1、テーマ:
n個の整数を含む配列numsが与えられ、a+b+c=0となるように、numsに3つの要素a,b,cが存在するか否かが判断される.条件を満たし、繰り返さないすべての三元グループを見つけます.
注意:答えに重複する三元グループは含まれてはいけません.

  ,      nums = [-1, 0, 1, 2, -1, -4]，

           ：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

2、構想分析:
さっき私もこの問題を迅速にソートする考えに言及しました.素晴らしい解題の考え方です.ここで、皆さんに提供したいのもこの解題の考え方です.
みんなはこの問題を見てきっと瞬間的に3層の循環を使うことを考えて、とても簡単ではありませんか?はい、しかし、この考えは考えてみればいいですが、実際の応用ではtime complexityは(n^3)のアルゴリズムで、やむを得ない限り、使用することをお勧めしません.
次の間にLeetCodeで11.最も多くの水を盛る容器を速く排出する思想で実現したのは、3 sumという問題はあなたにとって難しくありません.この問題の特徴を分析して、3つの数を見つけて0にするには、3つの数がすべて0の場合を除いて、必ず負数と正数があります.私たちはまずfixの1つの数を探して、それから他の2つの数を探して、私たちは2つの数を見つけて、最初のfix数の反対の数であればいいのですが、どのようにもっと効果的に位置づけることができますか?すべての2つの数の組合せを遍歴することは望ましくないでしょう.したがって、配列が秩序化されている場合、2つのポインタを使用して、問題の意味を満たすすべての2つの数の組合せを線形時間複雑度で遍歴することができます.この問題、それはおめでとうございます.あなたはこのアルゴリズムの大半を知っています.
元の配列をソートし、ソート後の配列をループし始めます.ここでは最後の停止までループするのではなく、最後から3番目にループすればいいことに注意します.ここで私たちはまず枝を切って最適化することができます.正数に遍歴するとbreakになります.なぜですか.私たちの配列は今秩序があるからです.もし最初のfixの数が正数であれば、後ろの数字は正数で、永遠に0に現れません.それから私たちはまた繰り返してスキップする処理を加えて、処理方法は2番目の数から始めて、前の数字と等しいならば、スキップして、私たちは同じ数字fixを2回したくないためです.遍歴した数については、0からこのfixの数を減算してtargetを1つ得、その後、2つの数の和がtargetに等しいことを見つけるだけでよい.2つのポインタを用いてfix数字の後から始まる配列の先頭と末尾の2つの数をそれぞれ指し,2つの数とちょうどtargetであれば,この2つの数とfixの数を一緒に結果に格納する.次に、重複する数値をスキップする手順で、両方のポインタが重複する数値を検出する必要があります.2つの数の和がtargetより小さい場合、左のポインタstartを右に移動して、指す数字を大きくします.同様に、2つの数の和がtargetより大きい場合、右のポインタendを左に1つシフトし、指す数字を少し小さくします.
Grandyangが明確なアルゴリズムの説明を提供してくれてありがとう、神様に感謝します!
大神のブログリンクを添付します.https://www.cnblogs.com/grandyang/p/4481576.html
3、コード実現:
C++実装

class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> res;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); ++k) {
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int target = 0 - nums[k];
            int i = k + 1, j = nums.size() - 1;
            while (i < j) {
                if (nums[i] + nums[j] == target) {
                    res.push_back({nums[k], nums[i], nums[j]});
                    while (i < j && nums[i] == nums[i + 1]) ++i;
                    while (i < j && nums[j] == nums[j - 1]) --j;
                    ++i; --j;
                } else if (nums[i] + nums[j] < target) ++i;
                else --j;
            }
        }
        return res;
    }
};

実行時間:104 msが81.54%のコミットユーザーに勝った
Java実装:

class Solution {
     public List> threeSum(int[] num) {
    Arrays.sort(num);
    List> res = new LinkedList<>(); 
    for (int i = 0; i < num.length-2; i++) {
        if (i == 0 || (i > 0 && num[i] != num[i-1])) {
            int lo = i+1, hi = num.length-1, sum = 0 - num[i];
            while (lo < hi) {
                if (num[lo] + num[hi] == sum) {
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
                    while (lo < hi && num[lo] == num[lo+1]) lo++;
                    while (lo < hi && num[hi] == num[hi-1]) hi--;
                    lo++; hi--;
                } 
                else if (num[lo] + num[hi] < sum) lo++;
                else hi--;
           }
        }
    }
    return res;
    }
}

実行時間:84 msで56.92%のコミット・ユーザーに勝利
Python実装:

def threeSum(nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        the capacibility of python original sort method is better than quick_sort
        """
        # new_nums = self.quick_sort(nums, 0, len(nums)-1)
        nums.sort()
        start, end ,sum = 0,0,0
        result = []  
        for i in range(len(nums)-2):
            if i==0 or (i>0 and nums[i]!=nums[i-1]): # ensure result has no repeat list
                sum = 0 - nums[i]
                start = i+1
                end = len(nums)-1               
                while start < end:
                    if nums[start] + nums[end] == sum: 
                        each_list = [nums[i], nums[start], nums[end]]
                        result.append(each_list)
                        while start < end and nums[start]==nums[start+1]:
                            start +=1
                        while start < end and nums[end]==nums[end-1]:
                            end -=1
                        start +=1
                        end -=1
                    elif nums[start] + nums[end] < sum:
                        start +=1
                    elif nums[start] + nums[end] > sum:
                        end -=1
        return result

実行時間:1052 msが38.11%のコミット・ユーザーに勝った
4、比較分析を通じて、javaの実行効率が最も高いことがわかります.これも私がjavaに執着している理由です.
再び本題に解題の構想を提供してくれたブロガーたちに感謝し、犬たちは一緒に頑張ります~~~