好的，这次我们来详细讲解 LeetCode 第 15 题：三数之和（3Sum）。

1. 题目描述

题目链接：
https://leetcode.com/problems/3sum/

题目：
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有满足条件且不重复的三元组。

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

示例：

输入：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[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

约束条件：

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

2. 题意理解

我们要在数组里找到所有不重复的三元组，使得它们的和为 0。
关键难点在于：

1. 不能重复：比如 [-1,0,1] 和 [0,1,-1] 是同一个三元组，只能算一次。
2. 要找出所有可能，不是只找一个。

3. 思路演进

3.1 暴力法（不可行）

直接三重循环枚举 i, j, k，检查 sum 是否为 0，同时用集合去重。
时间复杂度 O(n³)，n=3000 时显然会超时，不可行。

3.2 利用哈希表优化到 O(n²)？

两数之和问题可以用哈希表 O(n) 解决，那么固定第一个数 a，在后面的数中找两数之和为 -a，似乎可以 O(n²)？

但去重很麻烦：比如数组 [-1, -1, 0, 1]，固定第一个 -1 时，可能找到 (-1, 0, 1)；固定第二个 -1 时，又可能找到 (-1, 0, 1)，结果重复。
去重需要判断很多情况，容易写错。

3.3 排序 + 双指针（最优常用解法）

这是标准解法，既保证 O(n²) 时间复杂度，又能方便去重。

步骤：

1. 排序数组
   排序后，相同的数会相邻，方便跳过重复元素。

2. 枚举第一个数 a
   遍历数组，下标为 i，a = nums[i]。
   如果 a > 0，因为数组已升序，后面不可能有三个数之和为 0，直接结束。

3. 对 a 去重
   如果 nums[i] == nums[i-1] 且 i > 0，说明这个 a 已经计算过，跳过，避免重复三元组。

4. 双指针找两数之和为 -a
   令左指针 l = i+1，右指针 r = n-1，目标 target = -a。
   在 l < r 时循环：

   • 如果 nums[l] + nums[r] == target：找到一个解 [a, nums[l], nums[r]]，加入结果。
     • 然后 l 右移，r 左移。
     • 同时跳过 l 重复值（while l<r and nums[l]==nums[l-1]: l++）
     • 跳过 r 重复值（while l<r and nums[r]==nums[r+1]: r--）
   • 如果和 < target：l 右移（需要增大和）
   • 如果和 > target：r 左移（需要减小和）

4. 详细示例推导

以 nums = [-1,0,1,2,-1,-4] 为例：

排序后：[-4, -1, -1, 0, 1, 2]

i=0, a=-4
l=1, r=5，target=4

• -1+2=1 < 4 → l++
• -1+2=1 < 4 → l++ (l=3, 0+2=2<4 → l=4, 1+2=3<4 → l=5 停止) 无解

i=1, a=-1
target=1
l=2, r=5：nums[l]=-1, nums[r]=2 → -1+2=1 == target ✅ 得 [-1, -1, 2]
然后 l=3, r=4：0+1=1 == target ✅ 得 [-1, 0, 1]
之后 l=4, r=3 停止

i=2, a=-1
检查 nums[2] == nums[1]? 是，跳过（避免重复）

i=3, a=0
target=0
l=4, r=5：1+2=3 > 0 → r-- 后 l=4, r=4 停止

i=4, a=1
target=-1
l=5, r=5 停止

结果：[[-1,-1,2],[-1,0,1]]

5. 代码实现（Python）

def threeSum(nums):
    nums.sort()
    n = len(nums)
    res = []
    
    for i in range(n):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i-1]:
            continue
            
        l, r = i+1, n-1
        target = -nums[i]
        
        while l < r:
            s = nums[l] + nums[r]
            if s == target:
                res.append([nums[i], nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l-1]:
                    l += 1
                while l < r and nums[r] == nums[r+1]:
                    r -= 1
            elif s < target:
                l += 1
            else:
                r -= 1
                
    return res

6. 复杂度分析

• 时间复杂度：O(n²)
  排序 O(n log n) + 外层循环 O(n) × 内层双指针 O(n) = O(n²) 主导。
• 空间复杂度：O(1) 或 O(n)（取决于排序是否用额外空间，Python 的 sort 是 O(n) 最坏情况）。

7. 关键点总结

1. 排序：让重复元素相邻，方便跳过。
2. 固定 a 去重：if i>0 and nums[i]==nums[i-1]: continue
3. 双指针内去重：找到一组解后，跳过所有与当前 nums[l] 和 nums[r] 相同的值。
4. 提前终止：当 a > 0 时，后面不可能有解。

这样就能高效且不重复地找到所有三数之和为 0 的组合。