利用双指针或哈希表简化数组处理

15.题目链接-来源：力扣（LeetCode）（中等）

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

思路：

暴力解法就不谈了，很直白但是肯定超时。至少需要优化到O(n²)才可能通过。
注意到要求三元组不可重复，这种时候显然就需要排序了，不然你怎么记得自己存没存过这个答案。一开始心头一惊，一般排序要用快排，实现起来还是蛮繁琐的（要写个寻找pivot然后递归的辅助函数）。然后想起来 Arrays.sort() 这个小东西，对java的基本类型采用的是快排，于是直接拿来。
接下来看看能不能从暴力O(n³)简化到O(n²)。
上一篇笔记提过这种组合查找的题目自然而然想到用哈希表查找，把某一层O(n)的遍历降为O(1)。用一个HashSet记录一遍表中的元素，那么直接枚举前两个数，然后哈希查找第三个数。注意细节，对于 [-4,2,3]，我们前两层得到[-4,2，]，第三个元素用哈希搜索的话，是会得到2的，但是我们只有一个2，显然是不对的。这里如果要求 v3 > v2的话也不行，因为这样无法处理[-4,2,2]，遂放弃哈希表。
然后看了题解才知道用双指针，感觉这里没见过这类题的话不容易想到，以后就知道这样用了，双指针跟哈希表一样也适用于这类把O(n²)遍历简化为O(n)的问题。不同的是，双指针处理可能有重复的元素更加容易一些，因为能记录下标信息，不会搞混。遍历数组得到第一个元素v1，对每一个v1之后的元素用双指针向中间查找，因为我们排过序了所以v2坐标向右增长一定是不递减的，v3一定是不递增的，所以三者之和大于0就是收缩v3下标，否则增长v2下标，直到相遇或者满足和等于0，跳出。
时间复杂度：O(n²)
空间复杂度：O(m) m是一个接近 $C_n^3$ 的数

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        
        List<List<Integer>> ret = new LinkedList<>();
        
        for (int i = 0; i < n - 2; i++) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                int k = n - 1;
                for (int j = i + 1; j < k; j++) {
                    if (j == i + 1 || nums[j] != nums[j - 1]) {
                        // k-span shrinks
                        while (nums[i] + nums[j] + nums[k] > 0 && k > j + 1) {
                            k--;
                        }
                        // check and collect
                        if (nums[i] + nums[j] + nums[k] == 0) {
                            List<Integer> ans = new LinkedList(List.of(nums[i], nums[j], nums[k]));
                            ret.add(ans);
                            continue;
                        } 
                    }
                }
            }
        }
        return ret;
    }
}