15. 三数之和

Origin: LeetCode 15

题目描述

给定一个整数数组 nums，判断是否存在三个元素 a + b + c = 0。找出所有不重复的三元组。

示例

Input: nums = [-1, 0, 1, 2, -1, -4] Output: [[-1, -1, 2], [-1, 0, 1]]

Explanation:

• -1 + 0 + 1 = 0
• -1 + -1 + 2 = 0
• 注意 [-1, 0, 1] 和 [0, 1, -1] 算重复，只保留一个

Input: nums = [0, 1, 1] Output: []

Input: nums = [0, 0, 0] Output: [[0, 0, 0]]

约束

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10

关键信息

• 先排序，固定一个数，剩下两个用双指针
• 去重：固定数和指针都要跳过重复值
• 和为 0，不是任意 target

Resolution

我的解法

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

解题思路

排序 + 固定一个数 + 双指针。三数之和变两数之和：

1. 排序后，外层 for 固定 nums[i]
2. left = i+1，right = 末尾，双指针找 nums[left] + nums[right] = -nums[i]
3. sum < 0 → left++（太小），sum > 0 → right—（太大）
4. 三处去重：i 跳过相邻相同，left 和 right 找到后也跳过相邻相同

踩坑

• 第一版用 Map 去重，逻辑复杂且指针移动方向不对
• 去重不能忘：i、left、right 三处都要跳过重复值，否则结果有重复三元组
• i 不在 left 和 right 之间，i 是固定的开头，left 和 right 在 i 后面收缩

复杂度

• 时间：O(n²)，外层 n × 内层双指针 n
• 空间：O(1)（不算排序和输出）