三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

  • 输入：nums = [0,1,1]

  • 输出：[]

  • 解释：唯一可能的三元组和不为 0 。

  • 输入：nums = [0,0,0]

  • 输出：[[0,0,0]]

  • 解释：唯一可能的三元组和为 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const ans = [];
    for (let i = 0; i < n - 2; i++) {
        const x = nums[i];
        if (i > 0 && x === nums[i - 1]) continue; // 跳过重复数字
        if (x + nums[i + 1] + nums[i + 2] > 0) break; // 优化一
        if (x + nums[n - 2] + nums[n - 1] < 0) continue; // 优化二
        let j = i + 1, k = n - 1;
        while (j < k) {
            const s = x + nums[j] + nums[k];
            if (s > 0) k--;
            else if (s < 0) j++;
            else {
                ans.push([x, nums[j], nums[k]]);
                for (j++; j < k && nums[j] === nums[j - 1]; j++); // 跳过重复数字
                for (k--; k > j && nums[k] === nums[k + 1]; k--); // 跳过重复数字
            }
        }
    }
    return ans;
};