【LeetCode Hot 100】15. 三数之和
题目描述
回忆一下之前做过的两数之和，用的是哈希表存储已经遍历过的元素。但是本题要求返回值中不能有重复元素，因此需要去重，强行用哈希表的话，去重操作会很复杂。
我们可以通过哪些方法来保证返回的数组中不包含重复的三元组？
- 先将整个数组进行排序，可以保证答案数组中有\((a,b,c)\)（其中\(a \le b \le c\)）且\((b,a,c)\)或\((c,a,b)\)这样的三元组不会同时出现在答案数组中。
- 跳过相同的元素（排序之后这样的元素是相邻的），比如如果数组的排列是\(\dots, a, b, c, c. \dots\)，将\((a,b,c)\)加入答案后下一个三元组仍然是\((a,b,c)\)，仍然满足要求，如果我们跳过相同的元素，这样的重复情形就不会出现在答案中。
看到这个题，最简单粗暴的想法依旧是使用三重循环进行逐个遍历，但是这种方法的时间复杂度为\(O(N^3)\)，很容易超时。那么我们就需要对其进行优化。要找到满足nums[i] + nums[j] + nums[k] = 0的所有三数组合，对于每个固定的元素nums[k]（k可以作为最外层循环从头到尾进行遍历），相当于找到和确定为0 - nums[k]的两个数。要在循环内部找到这两个数，能否通过双重循环以外的方式呢？我们可以使用双指针，将两个指针分别设置在k+1位置和数组的最后一个位置，当三数之和sum == 0时，说明我们找到了一个正确的三元组，加入答案数组中；当sum < 0时，说明nums[i] + nums[j] < -nums[k]，需要把这两数之和增大，由于数组已经排好序，我们就应该把左边的指针向右移动一格（当然此过程需要跳过重复元素）；当sum > 0时，情况类似，需要把右边的指针向左移动。
这种方法的正确性是如何得来的呢？考虑这种情况，某一时刻的三元组\((k,i,j)\)表示此时正在检查的三个数的下标，\(k\)在外层循环，对于内层来说是固定的，如果三数之和\(S \gt 0\)，我们把\(j\)减小直到\(j\prime\)停下来，说明\(n_k + n_i + n_{j\prime} \le 0\)而当\(j\prime \lt j \lt len\)时，都有\(S \gt 0\)，如果我们再把\(i\)向右移动，那么\(n_i\)只会更大，加上\(j\prime \lt j \lt len\)的\(n_j\)，三数之和\(S\)也会更大，自然也大于\(0\)，所以我们可以说\(j\prime \lt j \lt len\)这段区间的\(j\)已经被我们排除了，所以我们才可以放心地同时移动双指针。
// Java
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int k = 0; k < nums.length - 2; k++) {
if (nums[k] > 0) break;
if (k > 0 && nums[k] == nums[k - 1]) continue;
int i = k + 1, j = nums.length - 1;
while (i < j) {
int sum = nums[k] + nums[i] + nums[j];
if (sum < 0) {
while (i < j && nums[i] == nums[++i]) ;
} else if (sum > 0) {
while (i < j && nums[j] == nums[--j]) ;
} else {
res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
while (i < j && nums[i] == nums[++i]) ;
while (i < j && nums[j] == nums[--j]) ;
}
}
}
return res;
}
}