做vi的網站廣告門
優(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
的長度。