LeetCode 15 - 三数之和（3Sum）

问题描述

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。

请你返回所有和为 0 且不重复的三元组。

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

示例

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[4] + nums[5] = 0 + (-1) + 1 = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

1
2
3

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

1
2
3

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

约束条件

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

解题思路

这道题的核心思想是将三数之和转化为两数之和问题。我们可以：

固定一个数：遍历数组，将当前数作为三元组的第一个数
双指针寻找另外两个数：在剩余数组中用双指针寻找两个数，使得三数之和为 0
排序去重：先对数组排序，便于双指针操作和去重

为什么要排序？

排序的好处：

便于双指针操作：排序后可以根据和的大小移动指针
便于去重：相同的数会相邻，容易跳过重复元素
提前终止：如果当前数大于 0，后面的数都更大，不可能找到和为 0 的三元组

双指针的移动策略

对于固定的第一个数 nums[i]，我们需要在 nums[i+1:] 中找到两个数，使得三数之和为 0：

如果 nums[i] + nums[left] + nums[right] == 0：找到一个解
如果 nums[i] + nums[left] + nums[right] < 0：和太小，需要增大，left++
如果 nums[i] + nums[left] + nums[right] > 0：和太大，需要减小，right--

实现细节

让我们用一个具体的例子来演示算法的执行过程：

例子演示：nums = [-1,0,1,2,-1,-4]

步骤 1：排序

原数组：[-1, 0, 1, 2, -1, -4]
排序后：[-4, -1, -1, 0, 1, 2]
          ↑   ↑   ↑  ↑  ↑  ↑
          0   1   2  3  4  5

步骤 2：遍历固定第一个数

第一轮：i = 0, nums[i] = -4

1
2
3

数组：[-4, -1, -1, 0, 1, 2]
        ↑   ↑            ↑
        i   left        right

寻找 -4 + nums[left] + nums[right] = 0，即 nums[left] + nums[right] = 4

left = 1, right = 5：-1 + 2 = 1 < 4，left++
left = 2, right = 5：-1 + 2 = 1 < 4，left++
left = 3, right = 5：0 + 2 = 2 < 4，left++
left = 4, right = 5：1 + 2 = 3 < 4，left++
left = 5, right = 5：left >= right，结束

第二轮：i = 1, nums[i] = -1

1
2
3

数组：[-4, -1, -1, 0, 1, 2]
            ↑   ↑        ↑
            i   left     right

寻找 -1 + nums[left] + nums[right] = 0，即 nums[left] + nums[right] = 1

left = 2, right = 5：-1 + 2 = 1 = 1 ✅ 找到解：[-1, -1, 2]

找到解后，需要跳过重复元素：

left++：left = 3
right--：right = 4
检查 nums[left] == nums[left-1]？nums[3] = 0, nums[2] = -1，不相等
检查 nums[right] == nums[right+1]？nums[4] = 1, nums[5] = 2，不相等

继续寻找：

left = 3, right = 4：0 + 1 = 1 = 1 ✅ 找到解：[-1, 0, 1]

第三轮：i = 2, nums[i] = -1

由于 nums[2] == nums[1]，跳过重复元素。

第四轮：i = 3, nums[i] = 0

1
2
3

数组：[-4, -1, -1, 0, 1, 2]
                   ↑  ↑  ↑
                   i left right

寻找 0 + nums[left] + nums[right] = 0，即 nums[left] + nums[right] = 0

left = 4, right = 5：1 + 2 = 3 > 0，right--
left = 4, right = 4：left >= right，结束

最终结果

找到的三元组：[[-1, -1, 2], [-1, 0, 1]]

代码实现

func threeSum(nums []int) (res [][]int) {
    n := len(nums)
    sort.Ints(nums)  // 排序
    
    for i := 0; i < n-2; i++ {
        // 优化：如果当前数大于0，后面不可能有和为0的三元组
        if nums[i] > 0 {
            break
        }
        
        // 跳过重复的第一个数
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        
        left := i + 1
        right := n - 1
        
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            
            if sum == 0 {
                // 找到一个解
                res = append(res, []int{nums[i], nums[left], nums[right]})
                left++
                right--
                
                // 跳过重复的left
                for left < right && nums[left] == nums[left-1] {
                    left++
                }
                
                // 跳过重复的right
                for left < right && nums[right] == nums[right+1] {
                    right--
                }
                
            } else if sum < 0 {
                left++   // 和太小，增大left
            } else {
                right--  // 和太大，减小right
            }
        }
    }
    
    return
}

复杂度分析

时间复杂度：$O(n^2)$

排序：$O(n \log n)$
外层循环：$O(n)$
内层双指针：$O(n)$
总时间复杂度：$O(n \log n) + O(n^2) = O(n^2)$

空间复杂度：$O(1)$

除了存储结果的数组外，只使用了常数级别的额外空间。

关键收获

核心技巧

降维思想：将三数之和转化为两数之和问题
排序的妙用：既便于双指针操作，又便于去重
双指针技巧：根据和的大小决定指针移动方向

常见陷阱

忘记去重：
- 第一个数的去重：if i > 0 && nums[i] == nums[i-1]
- 找到解后的去重：跳过相同的 left 和 right
边界条件：
- 外层循环到 n-2：至少要留两个位置给 left 和 right
- 双指针的边界：left < right
优化细节：
- 当 nums[i] > 0 时可以提前终止
- 去重时要注意数组越界

Adrian Wang's blog