LeetCode 15. 三数之和：排序+双指针，去重是真正的考点

题目与暴力起点

LeetCode 15：给定数组，找出所有和为 0 的不重复三元组 [a, b, c]——注意两个关键词：所有（不是只找一个）与不重复（三元组不能重复，即使元素值相同）。

输入：nums = [-1, 0, 1, 2, -1, -4]
输出：[[-1, -1, 2], [-1, 0, 1]]
（注意 [-1, 0, 1] 只出现一次，尽管数组里有两个 -1）

暴力 O(n³)：三层循环枚举所有三元组，和为 0 收集——然后面对「去重」的噩梦：三元组的重复不是「下标重复」是「值组合重复」（[-1,0,1] 用了下标 0,1,3 又用了下标 2,1,4——值一样）——去重的暴力方案：结果集哈希去重（把三元组排序后序列化进 set）——能过，但丑——排序的智慧：排序后，相同值的元素相邻——「值组合重复」转化为「扫描时的相邻重复」——去重从「事后哈希」变成「事前跳过」——这就是先排序的第二个理由（第一个是双指针需要有序）。

排序 + 固定 + 双指针

主框架：排序 → 固定第一个数 nums[i] → 在 [i+1, n-1] 区间用双指针找两数之和 = -nums[i]——「三数之和」降维成「两数之和」（双指针版，排序后的有序数组）——双指针的机制：left 从 i+1 开始、right 从末尾开始——sum = nums[i] + nums[left] + nums[right]——sum < 0 → left 右移（变大）；sum > 0 → right 左移（变小）；sum = 0 → 收集结果——「双指针的移动逻辑」依赖有序性——这也是排序的必要性。

def three_sum(nums):
    nums.sort()
    res = []
    n = len(nums)
    for i in range(n - 2):
        if nums[i] > 0:                      # 剪枝 1：最小的都 > 0
            break
        if i > 0 and nums[i] == nums[i-1]:   # 去重 1：跳过重复的 i
            continue
        left, right = i + 1, n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s < 0:
                left += 1
            elif s > 0:
                right -= 1
            else:
                res.append([nums[i], nums[left], nums[right]])
                left += 1                     # 去重 2：跳过重复的 left
                right -= 1                    # 去重 3：跳过重复的 right
                while left < right and nums[left] == nums[left-1]:
                    left += 1
                while left < right and nums[right] == nums[right+1]:
                    right -= 1
    return res

去重：真正的考点，三处 if 各有道理

去重 1：跳过重复的 i（i > 0 and nums[i] == nums[i-1]）——固定第一个数时，同一个值上一次已经作为 i 固定过了——「重复的 i 会产生重复的三元组」——用 nums[i] == nums[i-1]（与前一个比）跳过——为什么是和前一个比而不是后一个：和后一个比会误杀合法组合（[0,0,0]——第一个 0 与第二个 0 相等——跳过第一个 0 就只剩一个 0 组不成三元组——「和前一个比」保留第一次出现——「保留第一次、跳过后续」是去重的标准姿势。去重 2 与 3：找到解后跳过重复的 left/right——找到一个解后，left 右移 right 左移——如果移动后的值与刚才相同，会产生重复三元组——while nums[left] == nums[left-1]: left += 1——「比较对象是移动前的值」（nums[left] == nums[left-1]——跳过与前一个相同的——「移动后的 left 与已收集的 left 比较」——这个方向容易写反——「去重的锚点是已收集的结果」——每处去重的比较方向，都锚定在「刚刚收集过什么」——写反了不是 WA 就是漏解。

剪枝 1：nums[i] > 0 提前 break——排序后最小的数都大于 0——后面全大于 0——不可能凑出 0——「排序带来的剪枝」——不排序就没有这个剪枝——剪枝从 O(n²) 的常数层面提速。

graph TD
    A[排序] --> B[固定 i + 双指针找两数]
    B --> C[去重 1: i 与前一个比 跳过]
    B --> D[去重 2/3: left/right 与已收集值比]
    E[剪枝: nums[i] > 0 提前 break]
    F[方向错误 → WA 或漏解<br/>锚点是「已收集的结果」]

复杂度与四数之和的推广

复杂度分析：排序 O(n log n) + 主循环 O(n²)（外层 O(n) × 双指针 O(n)）——总复杂度 O(n²)——空间 O(log n)（排序栈——不含结果集）。「为什么双指针是 O(n)」：left 与 right 各走最多 n 步、方向单调——「指针的单调移动」保证 O(n)——不会回头。

四数之和（LeetCode 18）：三数之和的直接推广——「再固定一个数」：外层再套一层 i，内层三数之和——「两层固定 + 双指针」= O(n³)——「四层的去重」：i 与 j 两层都要去重——「每层固定都要去重」的规律——「n 数之和」的通用模板：排序 → 固定 n-2 个数（每层去重）→ 最后一层双指针——「模板的泛化能力」——面试从三数之和问到四数之和，考的就是「你能不能把去重推广」。

与哈希解法的对比：三数之和也可以哈希（两数之和的哈希思想）——但「哈希去重」比「排序去重」更难写对（组合去重的复杂性）——排序+双指针在此场景完胜——「不是哈希不好，是去重哈希难写」——工具与场景的匹配。

三数之和的进阶：去重的深入与「n 数之和的泛化」

三数之和的进阶：去重的系统性分析与 n 数之和的泛化模板。「去重的深入分析」：「去重的正确性证明」：「排序后同一值相邻」（去重的核心依据——「保留第一次」的正确性（「组合的字典序」：排序后同一组合必然连续出现——「连续出现」才可能被相邻判断捕获——「不排序的哈希去重」的复杂度（「排序结果」的序列化成本——「去重的完整覆盖」：i 层、left 层、right 层三处——「三处缺一」的后果——「缺 i 去重」：重复的 i 产生重复组合——「缺 left/right 去重」：重复的 left/right 产生重复组合——「三处去重的必要性」逐一验证——「手工构造测试用例」（[-1,-1,-1,2,2] 类的边界——「测试用例」的去重覆盖。「n 数之和的泛化模板」：「递归版模板」：「kSum(nums, target, k, start)」的递归——「k=2 的基线」（双指针——「k>2 的递归」（固定一个 + (k-1)Sum——「递归模板」的代码——「去重在每个递归层」（每层固定都要去重——「通用模板」的泛化能力——「n 数之和」的全家族（两数、三数、四数——「模板的复用」——「面试的追问链」：三数→四数→n 数——「追问链」考的是「泛化能力」——「背模板」与「推模板」的分界——「推」的练习：亲手从 3 推到 4——「推的过程」暴露理解缺口。「去重与「不重复」的业务映射」：「去重」在工程中的影子：「报表的去重」（统计去重（「去重的语义」（按维度去重——「业务去重」的常见（「算法的去重」是业务去重的抽象——「报表/风控/交易」的去重场景——「工程」与「算法」的映射——「三数之和」的去重功力在工程中是「数据唯一性保障」的能力。三数之和的进阶总结：去重的正确性证明（字典序连续）+三处覆盖验证+n 数泛化的递归模板+去重的工程映射（数据唯一性）——「三数之和」的难度核心在「去重」——「去重」的本质是「组合的规范化」——「规范化」= 「排序+跳过重复锚点」——「规范化」的思想在数据工程中无处不在（唯一键、去重统计、幂等键——「算法的去重」与「工程的幂等」是同一思想的两个形态。

三数之和的高频问答：正确性证明、去重锚点与溢出陷阱

问题一：双指针移动为什么不会漏解？——这是面试官最爱追的正确性问题，值得把论证说顺：固定 i 之后，在有序区段上设当前和 s = nums[i] + nums[left] + nums[right]。当 s < 0 时，保持 right 不动，任何更靠左的 left 只会让和更小——「以当前 right 为右端、left 及其左侧」的组合全部无解，所以 left 右移排除的是不可能包含解的区域，不是猜测；s > 0 时对称地右移 right。于是每一步移动都是安全剪枝：该收集的都收集了、被跳过的必然无解——这就是正确性证明的全部。面试中能把「每次移动排除的是哪部分解空间」讲明白的候选人不多，讲清楚了就出彩。

问题二：找到解后连续跳过重复值，会不会误杀合法组合？——不会，因为去重的锚点是「已收集的历史」。收集 [nums[i], nums[left], nums[right]] 之后，跳过的只是「与刚收集的值完全相同」的位置。用 [0,0,0] 手推一遍最安心：i 固定为 0，left=1、right=2，s=0 收集 [0,0,0]；随后 left、right 各进一步变成 2 与 1，left < right 不成立，循环自然结束——三个 0 的组合恰好收集一次，既没有重复也没有被误杀。「去重跳过的是已出现的历史，不是未来的可能」——想清楚这句话，去重 while 的比较方向（和前一个比、和已收集的比）就永远不会写反。

问题三：LeetCode 18（四数之和）与 454（四数相加 II）的本质区别是什么？——18 在一个数组里选四个数且组合不重复：排序 + 两层固定 + 双指针 O(n³)，去重贯穿每一层固定。454 是四个数组各取一个数、统计凑出 target 的组合数：不同数组的同值不算重复，且只要计数不要枚举——最优解是分组哈希：前两个数组的所有两两和进哈希表（值 → 出现次数），再遍历后两个数组查「target − 和」的次数，O(n²) 时间 O(n²) 空间。两题并排的教训是「重复」的语义由题面定义决定解法——先问「什么算重复」，再选去重手段，顺序不能颠倒。18 还有一个工程细节：四个 int 相加可能溢出 32 位，数据范围大时必须用 long 累加中间和——溢出是四数之和里仅次于去重的第二大 WA 来源，也是面试官检查你严谨性的暗桩。

顺带补一个常被追问的细节：为什么去重要在「收集后立即跳过」而不是「收集前判断」？——收集后跳过的实现最短：left、right 各自与刚才收集的值比一次即可；收集前判断则需要额外维护「上一组解」的状态、逻辑分叉更多。两种写法都对，但前者出错面更小——面试写代码时优先选择「需要维护的状态最少」的写法，这既是去重这道考点的解法偏好，也是通用的工程直觉：状态越少，边界越少，bug 越少。

小结

三数之和的完整解析：暴力与排序的智慧（排序让「值重复」变「相邻重复」——去从事后哈希变事前跳过）；框架（排序 → 固定 i → 双指针找两数——三数之和降维成两数之和）；去重三处（i 与前一个比保留第一次、left/right 与已收集值比——「锚点是已收集的结果」）；剪枝（nums[i] > 0 提前终止）；推广（四数之和 = 两层固定 + 每层去重——n 数之和的通用模板）；哈希与双指针的对比（此场景排序去重完胜哈希去重）。给学习者的核心提醒：三数之和 90% 的 WA 在去重，去重 90% 的错误在比较方向——每写一个去重 if，问自己「我锚定的是已收集的结果吗」——以及，这道题的本质训练是「在有序数组上设计单调指针的移动规则」——这个能力在接雨水（库内已有）、/container with most water 等一整族题目中通用。

三数之和不是「更难的两数之和」，是「去重的系统工程」——从这一题学到的不去重功力，会在所有「收集所有解」类题目中反复回报。