[LeetCode][Python]15. 三數(shù)之和

給定一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，

滿足要求的三元組集合為：
[[-1, 0, 1],[-1, -1, 2]]

解題思路：

1. 暴力枚舉？
2. 還是沒有思路
   參考別人：
   先將給定nums排序，簡化問題，復(fù)雜度為O(nlogn)。

令nums[k] + nums[i] + nums[j] == 0，找所有的組合的思路是：遍歷三個數(shù)字中最左數(shù)字的指針k，找到數(shù)組中所有不重復(fù)k對應(yīng)所有b c組合，即每指向新的nums[k]，都通過雙指針法找到所有和為0的nums[i] nums[j]并記錄：

當(dāng)nums[k] > 0時，直接跳出，因?yàn)閖 > i > k，所有數(shù)字大于0，以后不可能找到組合了；

當(dāng)k > 0 and nums[k] == nums[k - 1]，跳過此數(shù)字，因?yàn)閚ums[k - 1]的所有組合已經(jīng)被加入到結(jié)果，如果本次搜索，只會搜索到重復(fù)組合。

i, j分設(shè)在[k, len(nums)]兩端，根據(jù)sum與0的大小關(guān)系交替向中間逼近，如果遇到等于0的組合則加入res中，需要注意：移動i j需要跳過所有重復(fù)值，否則重復(fù)答案會被計入res。

先排序再查找nlogn快排，第一層循環(huán)從起點(diǎn)位置開始枚舉a，從剩余數(shù)組中查找b和c。因?yàn)橄扰判蛄?，所以b和c可以向中間靠攏。如果a+b+c>0，則c從最右端向左移動一位。如果a+b+c<0，則b從最左端向右移動一位?？词欠竦扔?的情況。因?yàn)閎和c都是線性的往中間移動的，所以時間復(fù)雜度是O(N^2)。但是就地查找，沒有新開辟set空間，所以空間復(fù)雜度是O(1)。

    def threeSum2(self, nums):
        res = []
        nums.sort()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, len(nums) - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l += 1 # 左邊界向右移動一步
                elif s > 0:
                    r -= 1 # 右邊界向左移動一步
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    # 過濾重復(fù)的結(jié)果
                    while l < r and nums[l] == nums[l+1]:
                        l+=1
                    while l < r and nums[r-1] == nums[r]:
                        r -= 1
                    l += 1
                    r -= 1
        return res