leetcode🧑‍💻 15. 三数之和 [ ricepudding ]

双指针

解题思路

对数组进行升序排序，使用三个指针 i、j 和 k 分别代表要找的三个数，通过枚举 k 确定第一个数，另外两个指针 i、j 分别从左边 k + 1 和右边 n - 1 往中间移动，找到满足 nums[i] + nums[j] + nums[k] == 0 的所有组合；

j 和 k 指针的移动逻辑，分情况讨论 sum = nums[i] + nums[j] + nums[k]：

sum > 0：k 左移，使 sum 变小；

sum < 0：j 右移，使 sum 变大；

sum = 0：找到符合要求的答案，存起来；

如果 nums[k] > 0 那么后面的两个数一定都是大于 0 的，肯定无法满足 nums[i] + nums[j] + nums[k] == 0，则直接跳过；

还要去除重复结果：

nums[k] === nums[k−1] 则说明该数字重复，会导致结果重复，所以应该跳过；

当 sum == 0 时，nums[i] === nums[i+1] 则会导致结果重复，应该跳过，i++；

当 sum == 0 时，nums[j] == nums[j−1] 则会导致结果重复，应该跳过，j−−；

复杂度

时间复杂度 O(N^2)：数组排序 O(NlogN)，遍历数组+双指针遍历 O(N^2)，总体 O(NlogN) + O(N^2)；
空间复杂度 O(1)；

代码实现

var threeSum = function (nums) {
    const res = [];
    if (nums.length < 3) return res;

    // 1. 数组排序
    nums.sort((a, b) => a - b);
    let i, j;

    // 2. 固定一个指针，另外两个指针根据求和的大小，向内收缩
    for (let k = 0; k < nums.length - 2; k++) {
        // - nums[k] === nums[k−1] 则说明该数字重复，会导致结果重复，所以应该跳过
        // - nums[k] > 0 那么后面的两个数一定都是大于 0 的，无法满足 `nums[i] + nums[j] + nums[k] == 0`，则直接跳过；
        if (nums[k] > 0 || nums[k] == nums[k - 1]) continue;

        i = k + 1;
        j = nums.length - 1;
        while (i < j) {
            if (nums[k] + nums[i] + nums[j] > 0) {
                j--;
            } else if (nums[k] + nums[i] + nums[j] < 0) {
                i++;
            } else {
                res.push([nums[k], nums[i], nums[j]]);

                // 去掉重复情况
                while (i < j && nums[i + 1] == nums[i]) i++;
                while (i < j && nums[j - 1] == nums[j]) j--;
                i++;
                j--;
            }
        }
    }

    return res;
};