015.三数之和.md

题目描述

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

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

示例

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路

首先对数组进行排序，然后先确定一个数字，再去找另外两个满足条件的数字。遇到重复的数字则跳过。
当确定一个数后，采用双指针的方式，从排好序的数组两端开始遍历来找到所有满足条件的另外两个数字。

代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
let threeSum = function(nums) {
    let res = [];
    // 排序
    nums.sort((a, b) => a - b);
    // 如果全部大于0或全全部小于0则无满足条件的情况
    if (nums[0] > 0 || nums[nums.length - 1] < 0) {
        return res;
    }
    for (let i = 0, l = nums.length - 2; i < l; i++) {
        // 如果当前数与上一个重复则跳过
        if (i > 0 && nums[i - 1] === nums[i]) {
            continue;
        }
        // 利用双指针查询满足nums[i]的另外两个数
        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) {
            // 总和小于0 左边右移 同时跳过重复的数
            if (nums[i] + nums[left] + nums[right] < 0) {
                while (left < right && nums[left] === nums[++left]) {}
            }
            // 总和大于0 右边左移 同时跳过重复的数
            else if (nums[i] + nums[left] + nums[right] > 0) {
                while (left < right && nums[right] === nums[--right]) {}
            }
            // 满足条件 左边右移 右边左移 同时跳过重复的数
            else {
                res.push([nums[i], nums[left], nums[right]]);
                while (left < right && nums[left] === nums[++left]) {}
                while (left < right && nums[right] === nums[--right]) {}
            }
        }
    }
    return res;
};