15.三数之和

[Geekhyt]

原题链接

先明确，题目不仅是要求 a + b + c = 0，而且需要三个元素都不重复。

所以我们可以先将数组从小到大排序，排序后，去除重复项会更加简单。

1.外层循环指针 i 遍历数组，题目要求三数之和为 0，考虑此次循环中的数若大于 0，另外两个数肯定也大于 0，则当前位置下无解。
2.去重，如果当前元素和前一个元素相同时，直接跳过即可。
3.内层循环借助双指针夹逼求解，两个指针收缩时也要去除重复的位置。
4.三数之和为 0 时，将当前三个指针位置的数字推入数组即所求。若当前和小于 0 则将左指针向右移动，若当前和大于 0 则将右指针向左移动。

const threeSum = function(nums) {
    const result = []
    const len = nums.length
    if (len < 3) {
        return result
    }
    nums.sort((a, b) => a - b)
    for (let i = 0; i < len - 2; i++) {
        if (nums[i] > 0) {
            break
        }
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue
        }
        let L = i + 1
        let R = len - 1
        while (L < R) {
            let sum = nums[i] + nums[L] + nums[R]
            if (sum === 0) {
                result.push([nums[i], nums[L], nums[R]])
                while(nums[L] === nums[L + 1]){
                    L++
                }
                while(nums[R] === nums[R - 1]){
                    R--
                }
                L++
                R--
            } else if (sum < 0) {
                L++
            } else {
                R--
            }
        }
    }
    return result
}

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)