【LeetCode分享】三数之和

题目描述 15. 三数之和

给你一个包含 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]]

示例2
输入：nums = []
输出：[]

示例3
输入：nums = [0]
输出：[]

提示：

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

解题思路

由于输出的是不重复的组合，如果我们直接从数组第一个数开始遍历的话，得到的解可能有重复，最后再去去重的话时间复杂度就比较高了。对于这种要求不重复的，一般考虑是哈希表，不过此处的三元组中可以有重复元素，故哈希表不适合在此处，另一种考虑就是如果是一个单增/减数列的话，也可以保证不重复，此处我们可以先对数组进行排序，变成一个单增数组，再进一步考虑。
对于数组排序，JavaScript实现方式很简单，时间复杂度是

nums.sort((a, b) => {
        return a - b
    })

当对数组排序后，对于这个单调不减的数组，我们可以对数组的元素进行遍历，令，考虑当时停止，因为，则已经不满足了。
当我们确定了之后，可以用两个指针分别指向数组的下一个元素以及数组的最后一个元素，得到数，求得，如果：

1. ，满足条件，指针往后移动到不重复的元素位置，j++，k--且分别跳过重复的元素。
2. ，说明三数之和过大，需要将往左移。
3. ，说明三数之和过小，需要将往右移。
4. 注意的是，指针一定是在指针的左侧，即满足j < k。

JavaScript实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    const n = nums.length
    if (nums == null || n < 3) return []
    const res = []
    // 先进行排序
    nums.sort((a, b) => {
        return a - b
    })
    // console.log(nums)
    for (let i = 0; i < n - 2; i++) {
        // 跳过重复元素
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue
        }
        // 设置双指针分别为 (i, nums.length)，在区间进行查找
        let j = i + 1,
            k = n - 1
        while (j < k) {
            let s = nums[i] + nums[j] + nums[k]
            if (s === 0) {
                res.push([nums[i], nums[j], nums[k]])
                // 去重
                while (j < k && nums[j] === nums[j + 1]) j++
                while (j < k && nums[k] === nums[k - 1]) k--
                j++
                k--
            } else if (s > 0) {
                k--
            } else if (s < 0) {
                j++
            }
        }
    }
    return res
}
// test
console.log(threeSum([-1, 0, 1, 2, -1, -4]))