15.三数之和

排序+双指针

题目要求找出所有和为 $0$ 的不重复三元组。一个很自然的想法是先固定一个数，再去剩余部分中寻找两个数，使三者和为 $0$。

为了高效寻找这两个数，可以先对数组排序。这样在固定 $nums[k]$ 后，就能在区间 $[0, k - 1]$ 中使用双指针查找两数之和是否等于 $-nums[k]$。如果当前和偏小，就让左指针右移；如果当前和偏大，就让右指针左移；如果恰好相等，就记录答案。

排序之后还可以方便地去重。固定的第三个数如果和上一次相同，就直接跳过；找到一组合法答案后，也要分别跳过左侧和右侧的重复元素，避免加入重复三元组。

时间复杂度 $O(n^2)$

空间复杂度 $O(\log n)$

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int k = nums.length - 1; k >= 2; k--) {
            if (k < nums.length - 1 && nums[k] == nums[k + 1]) {
                continue;
            }
            int i = 0, j = k - 1;
            while (i < j) {
                if (nums[i] + nums[j] == -nums[k]) {
                    ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    while (i < j && nums[i] == nums[i + 1]) {
                        i++;
                    }
                    while (i < j && nums[j] == nums[j - 1]) {
                        j--;
                    }
                    j--;
                    i++;
                } else if (nums[i] + nums[j] < -nums[k]) {
                    i++;
                } else {
                    j--;
                }
            }
        }
        return ans;
    }
}