By Long Luo
15. 三數(shù)之和題目如下：
- 三數(shù)之和
給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums猎莲，判斷 nums 中是否存在三個(gè)元素 a，b嘹裂，c 锄弱，使得 a + b + c = 0 虽另？請你找出所有和為 0 且不重復(fù)的三元組础锐。
注意：答案中不可以包含重復(fù)的三元組。
示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
示例 2：
輸入：nums = []
輸出：[]
示例 3：
輸入：nums = [0]
輸出：[]
提示：
0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
方法一：暴力遍歷
思路與算法：
“不重復(fù)”的本質(zhì)是什么辜御？
我們保持三重循環(huán)的大框架不變伍派，只需要保證：
- 第二重循環(huán)枚舉到的元素不小于當(dāng)前第一重循環(huán)枚舉到的元素江耀；
- 第三重循環(huán)枚舉到的元素不小于當(dāng)前第二重循環(huán)枚舉到的元素。
也就是說诉植，我們枚舉的三元組滿足
祥国，保證了只有
這個(gè)順序會被枚舉到，而
晾腔、
等等這些不會舌稀，這樣就減少了重復(fù)。要實(shí)現(xiàn)這一點(diǎn)建车，我們可以將數(shù)組中的元素從小到大進(jìn)行排序扩借，隨后使用普通的三重循環(huán)就可以滿足上面的要求。
由于結(jié)果肯定會出現(xiàn)重復(fù)的數(shù)字缤至，所以我們使用Set來去重潮罪，代碼如下所示：
public static List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 3) {
return new ArrayList<>();
}
Set<List<Integer>> res = new HashSet<>();
int n = nums.length;
// O(NLogN)
Arrays.sort(nums);
// O(N^3)
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
res.add(list);
}
}
}
}
return new ArrayList<>(res);
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
康谆，其中N是數(shù)組
的長度。
- 空間復(fù)雜度：
嫉到。
方法二：排序 + 雙指針
思路與算法：
方法一肯定會超時(shí)沃暗，所以我們需要使用更好的方法。
使用雙指針的方法何恶，將枚舉的時(shí)間復(fù)雜度從減少至
孽锥。
為什么是呢？這是因?yàn)樵诿杜e的過程每一步中细层，左指針會向右移動一個(gè)位置惜辑，而右指針會向左移動若干個(gè)位置，這個(gè)與數(shù)組的元素有關(guān)疫赎，但我們知道它一共會移動的位置數(shù)為
盛撑，均攤下來，每次也向左移動一個(gè)位置捧搞，因此時(shí)間復(fù)雜度為
抵卫。
但考慮到問題的解決，代碼中需要注意一些去重技巧胎撇。
public static List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 3) {
return new ArrayList<>();
}
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < n - 2; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = n - 1;
int target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else if (sum == target) {
ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
//
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
}
}
}
return ans;
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
介粘，其中N是數(shù)組
- 空間復(fù)雜度：
晚树。
這道題我在做的時(shí)候姻采，看了解題之后，對sum==target之后爵憎，一定要做left++; right--有點(diǎn)不解偎谁，不可以只left++或者right--嗎？
后來才想到纲堵，現(xiàn)在已經(jīng)sum==target，如果只處理一邊闰渔，那得到的不還是重復(fù)的數(shù)據(jù)嗎席函？所以需要兩邊操作，然后如果還是遇到重復(fù)的數(shù)字冈涧，那還需要繼續(xù)處理茂附。
原文鏈接：15. 三數(shù)之和
