題目

給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？請(qǐng)你找出所有和為 0 且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。
示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
示例 2：
輸入：nums = []
輸出：[]
示例 3：
輸入：nums = [0]
輸出：[]

解析

最直接的想法，數(shù)組的三個(gè)位置做三重循環(huán)，枚舉所有的三元組，復(fù)雜度達(dá)到了，在這之后，我們還需要使用哈希表進(jìn)行去重操作，得到不包含重復(fù)三元組的最終答案，又消耗了大量的空間。這顯然是不現(xiàn)實(shí)的，故而我們考慮要縮小搜索范圍。
關(guān)鍵條件是“不重復(fù)”。我們完全可以假設(shè)結(jié)果的三元組（a,b,c) 是滿(mǎn)足遞增順序的，這不影響結(jié)果的完備性。
為了實(shí)現(xiàn)這點(diǎn)，只需要保證：
1，第二重循環(huán)枚舉到的元素不小于當(dāng)前第一重循環(huán)枚舉到的元素；（b≥a）
2，第三重循環(huán)枚舉到的元素不小于當(dāng)前第二重循環(huán)枚舉到的元素。（c≥b）
所以，我們首先進(jìn)行排序，python中的sort()即可遞增的排序。

同時(shí)，對(duì)于每一重循環(huán)而言，相鄰兩次枚舉的元素不能相同，否則也會(huì)造成重復(fù)。舉個(gè)例子，如果排完序的數(shù)組為[0, 1, 2, 2, 2, 3]。
我們使用三重循環(huán)枚舉到的第一個(gè)三元組為 (0, 1, 2)，如果第三重循環(huán)繼續(xù)枚舉下一個(gè)元素，那么仍然是三元組 (0, 1, 2)，產(chǎn)生了重復(fù)。因此我們需要將第三重循環(huán)「跳到」下一個(gè)不相同的元素，即數(shù)組中的最后一個(gè)元素 3，枚舉三元組 (0, 1, 3)。偽代碼如下：

nums.sort()
for first = 0 .. n-1
    // 只有和上一次枚舉的元素不相同，我們才會(huì)進(jìn)行枚舉
    if first == 0 or nums[first] != nums[first-1] then
        for second = first+1 .. n-1
            if second == first+1 or nums[second] != nums[second-1] then
                for third = second+1 .. n-1
                    if third == second+1 or nums[third] != nums[third-1] then
                        // 判斷是否有 a+b+c==0
                        check(first, second, third)

但這樣并沒(méi)有脫離三重循環(huán)的大框架，復(fù)雜度依然是。
然而它是很容易繼續(xù)優(yōu)化的，可以發(fā)現(xiàn)，如果我們固定了前兩重循環(huán)枚舉到的元素 a 和 b，那么只有唯一的 c 滿(mǎn)足 a+b+c=0。當(dāng)?shù)诙匮h(huán)往后枚舉一個(gè)元素 b'時(shí)，由于 b' > b，那么滿(mǎn)足 a+b'+c'=0的 c'一定有 c' < c，即 c'在數(shù)組中一定出現(xiàn)在 c 的左側(cè)。也就是說(shuō)，我們可以從小到大枚舉 b，同時(shí)從大到小枚舉 c，即第二重循環(huán)和第三重循環(huán)實(shí)際上是并列的關(guān)系。

有了這樣的發(fā)現(xiàn)，我們就可以保持第二重循環(huán)不變，而將第三重循環(huán)變成一個(gè)從數(shù)組最右端開(kāi)始向左移動(dòng)的指針，從而得到下面的偽代碼：

nums.sort()
for first = 0 .. n-1
    if first == 0 or nums[first] != nums[first-1] then
        // 第三重循環(huán)對(duì)應(yīng)的指針
        third = n-1
        for second = first+1 .. n-1
            if second == first+1 or nums[second] != nums[second-1] then
                // 向左移動(dòng)指針，直到 a+b+c 不大于 0
                while nums[first]+nums[second]+nums[third] > 0
                    third = third-1
                // 判斷是否有 a+b+c==0
                check(first, second, third)

這個(gè)方法就是我們常說(shuō)的「雙指針」，當(dāng)我們需要枚舉數(shù)組中的兩個(gè)元素時(shí)，如果我們發(fā)現(xiàn)隨著第一個(gè)元素的遞增，第二個(gè)元素是遞減的，那么就可以使用雙指針的方法，將枚舉的時(shí)間復(fù)雜度從 減少至。為什么是呢？這是因?yàn)樵诿杜e的過(guò)程每一步中，「左指針」會(huì)向右移動(dòng)一個(gè)位置（也就是題目中的 b），而「右指針」會(huì)向左移動(dòng)若干個(gè)位置，這個(gè)與數(shù)組的元素有關(guān)，但我們知道它一共會(huì)移動(dòng)的位置數(shù)為 ，均攤下來(lái)，每次也向左移動(dòng)一個(gè)位置，因此時(shí)間復(fù)雜度為 。

注意到我們的偽代碼中還有第一重循環(huán)，時(shí)間復(fù)雜度為 ，因此枚舉的總時(shí)間復(fù)雜度為 。由于排序的時(shí)間復(fù)雜度為 ，在漸進(jìn)意義下小于前者，因此算法的總時(shí)間復(fù)雜度為 。

上述的偽代碼中還有一些細(xì)節(jié)需要補(bǔ)充，例如我們需要保持左指針一直在右指針的左側(cè)（即滿(mǎn)足 b≤c），具體可以參考下面的代碼，均給出了詳細(xì)的注釋。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        # 枚舉 a
        for first in range(n):
            # 需要和上一次枚舉的數(shù)不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 對(duì)應(yīng)的指針初始指向數(shù)組的最右端
            third = n - 1
            target = -nums[first]
            # 枚舉 b
            for second in range(first + 1, n):
                # 需要和上一次枚舉的數(shù)不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保證 b 的指針在 c 的指針的左側(cè)
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指針重合，隨著 b 后續(xù)的增加
                # 就不會(huì)有滿(mǎn)足 a+b+c=0 并且 b<c 的 c 了，可以退出循環(huán)
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        
        return ans

復(fù)雜度分析:
時(shí)間復(fù)雜度：。
空間復(fù)雜度：。