優(yōu)質博文：IT-BLOG-CN

一、題目

給你一個整數數組nums，判斷是否存在三元組[nums[i], nums[j], nums[k]]滿足i != j、i != k且j != k，同時還滿足nums[i] + nums[j] + nums[k] == 0。請你返回所有和為0且不重復的三元組。

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

示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0
不同的三元組是[-1,0,1]和[-1,-1,2]
注意，輸出的順序和三元組的順序并不重要。

示例 2：
輸入：nums = [0,1,1]
輸出：[]
解釋：唯一可能的三元組和不為0

示例 3：
輸入：nums = [0,0,0]
輸出：[[0,0,0]]
解釋：唯一可能的三元組和為0

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

二、代碼

排序 + 雙指針： 題目中要求找到所有「不重復」且和為0的三元組，這個「不重復」的要求使得我們無法簡單地使用三重循環(huán)枚舉所有的三元組。這是因為在最壞的情況下，數組中的元素全部為0，即[0,0,0,0,0]任意一個三元組的和都為0。如果我們直接使用三重循環(huán)枚舉三元組，會得到O(N3)個滿足題目要求的三元組（其中N是數組的長度）時間復雜度至少為O(N3)。在這之后，我們還需要使用哈希表進行去重操作，得到不包含重復三元組的最終答案，又消耗了大量的空間。這個做法的時間復雜度和空間復雜度都很高，因此我們要換一種思路來考慮這個問題。

「不重復」的本質是什么？我們保持三重循環(huán)的大框架不變，只需要保證：第二重循環(huán)枚舉到的元素不小于當前第一重循環(huán)枚舉到的元素；第三重循環(huán)枚舉到的元素不小于當前第二重循環(huán)枚舉到的元素。

也就是說，我們枚舉的三元組(a,b,c)滿足a≤b≤ca，保證了只有(a,b,c)這個順序會被枚舉到，而(b,a,c)(c,b,a)等等這些不會，這樣就減少了重復。要實現(xiàn)這一點，我們可以將數組中的元素從小到大進行排序，隨后使用普通的三重循環(huán)就可以滿足上面的要求。同時，對于每一重循環(huán)而言，相鄰兩次枚舉的元素不能相同，否則也會造成重復。舉個例子，如果排完序的數組為[]1,2,2,2,4]

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

這種方法的時間復雜度仍然為O(N3)，畢竟我們還是沒有跳出三重循環(huán)的大框架。然而它是很容易繼續(xù)優(yōu)化的，可以發(fā)現(xiàn)，如果我們固定了前兩重循環(huán)枚舉到的元素a和b，那么只有唯一的c滿足a+b+c=0。當第二重循環(huán)往后枚舉一個元素b時，由于b′>b，那么滿足a+b′+c′=0的c′一定有c′<c，即c′在數組中一定出現(xiàn)在c的左側。也就是說，我們可以從小到大枚舉b，同時從大到小枚舉c，即第二重循環(huán)和第三重循環(huán)實際上是并列的關系。

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

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

這個方法就是我們常說的「雙指針」，當我們需要枚舉數組中的兩個元素時，如果我們發(fā)現(xiàn)隨著第一個元素的遞增，第二個元素是遞減的，那么就可以使用雙指針的方法，將枚舉的時間復雜度從O(N2)減少至O(N)。為什么是O(N)呢？這是因為在枚舉的過程每一步中，「左指針」會向右移動一個位置（也就是題目中的b），而「右指針」會向左移動若干個位置，這個與數組的元素有關，但我們知道它一共會移動的位置數為O(N)，均攤下來，每次也向左移動一個位置，因此時間復雜度為O(N)。

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

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

class Solution {public List<List<Integer>> threeSum(int[] nums) {//思想：1、先對 nums 進行排序// 2、先確定第一層循環(huán)，通過 0 - nums[x] 得到第二層和第三層的和// 3、將第二層和第三層匯總為一層，left = i + 1; right = nums.length - 1; 進行雙指針移動，計算和，如果相等，加入隊列，并繼續(xù)移動指針，直到不滿足 left < rightint left = 0, right = 0, size = 0;List<List<Integer>> res = new ArrayList();Arrays.sort(nums);for(int i = 0; i < nums.length; i++) {if (i > 0 && i < nums.length && nums[i] == nums[i-1]) {continue;}// i 發(fā)生變化之后，left 和 right 指針都需要發(fā)生變化。 第一次將right定義再外部，導致bugleft = i + 1;right = nums.length - 1;int tar = -nums[i];while(left < right) {if (nums[left] + nums[right] == tar) {List<Integer> temp = Arrays.asList(nums[i], nums[left], nums[right]);res.add(temp);// 數據去重while(left < right && nums[left] == nums[left + 1]) {++left;}while(right > left && nums[right] == nums[right - 1]) {--right;}++left;--right;} else if(nums[left] + nums[right] < tar){++left;} else {--right;}}}return res;}
}

時間復雜度： O(N2)其中N是數組nums的長度。
時間復雜度： O(N2)，其中N是數組nums的長度。