三数之和（LeetCode #15）
三数之和要求返回所有和为零、按值去重的三元组。先排序，固定一个锚点，再用双指针扫描后缀，将暴力 O(n³) 降为 O(n²)。重复值相邻，可以直接跳过，不必另建去重集合。
排序花 O(n log n)，同时带来两个条件：左端候选最小、右端最大，指针排除规则成立；相等值挨在一起，锚点和两侧指针都能用邻居比较去重。
三数之和如何工作
固定候选三元组最小位置 nums[i] 为锚点，其余两值之和应为 need = -nums[i]。这就是在有序后缀上执行双指针搜索。lo 从锚点右侧开始，hi 从末尾开始。
和小于 need 时，当前左值连最大的可用右值都不够，推进 lo；和大于 need 时，当前右值连最小的可用左值都偏大，后退 hi。相等则记录 [nums[i], nums[lo], nums[hi]]。
三项细节都依赖有序性：
- 跳过重复锚点：i > 0 且
nums[i] == nums[i - 1]时，前一锚点已扫描更大的同目标后缀，本轮只能重复。 - 命中后两端都移动，再跳过同值：固定锚点时，保持一端而让另一端变化，只可能因相同值再次命中，得到重复三元组。两端移动后，分别跳过刚使用值的连续副本。
- 正锚点结束全部搜索：
nums[i] > 0时，后面都不更小，任何剩余三元组和都为正。使用break，无需继续锚点循环。
逐步演示
默认 nums = [-1, 0, 1, 2, -1, -4]。
- 排序：得到
[-4, -1, -1, 0, 1, 2]，两个 -1 相邻。 - 索引 0，锚点 -4，need = 4：依次检查
-1 + 2 = 1、-1 + 2 = 1、0 + 2 = 2、1 + 2 = 3。都不足 4，lo 走到与 hi 相遇，本锚点无结果。 - 索引 1，锚点 -1，need = 1：
-1 + 2 = 1命中，记录[-1, -1, 2]。两指针内移到 0、1，没有重复跳过。 - 继续同一锚点：
0 + 1 = 1，记录[-1, 0, 1]，两指针移动后交叉。一个锚点可以产生多组解。 - 索引 2 的 -1：等于左邻居，跳过。它能扫描的候选只是上一轮的子集。
- 索引 3，锚点 0，need = 0：唯一候选
1 + 2 = 3 > 0，hi 后退，指针相遇。锚点最多到n - 3，之后不足三个位置。 - 完成：结果
[[-1, -1, 2], [-1, 0, 1]]，每组恰好一次。
画布用紫色标锚点，标题显示 need，括号与双指针展示一次两数搜索。排除的格子变淡，锚点前的格子保留为已处理历史。每次配对检查让 tests 加一，最多 n 个锚点各扫描 O(n)，形成 O(n²)。
默认数据不会触发命中后的左右去重循环，因为相邻值恰好不重复。切到配置中的 Duplicates everywhere，观察两端越过同值段；没有这两个循环就会再次记录同一组三元组。
时间与空间复杂度
| 方法 | 时间 | 扫描工作区，不含输出和另列成本 | 去重 |
|---|---|---|---|
| 枚举每组三元组 | O(n³) | O(1) | 若用规范化三元组集合，另需 O(k) 保存 k 个不同结果 |
| 排序、锚点、双指针 | O(n²) | O(1) | 相邻跳过，无额外集合 |
排序 O(n log n) 被总扫描 O(n²) 覆盖。常数空间只指双指针层，不包含输出和排序工作区；Python Timsort 最坏可使用 O(n) 辅助空间。输入面板最多八个、范围 −20 到 20 的值，只为显示清楚。
目标不必为零，可改为 need = target - nums[i]；提前结束条件也要改成 3 * nums[i] > target，因为锚点是三个值中最小的，三元组之和至少为 3 * nums[i]。保留 nums[i] > 0 的话，[1, 2, 3]、target 6 会在第一个锚点就停下，漏掉答案。k-sum 也可逐层固定锚点，递归到有序 2Sum，再用线性扫描结束。需要按值去重且允许排序时适合这套结构。nums.sort() 会原地改序；调用者需要原顺序时先复制。
边界情况
- 恰好三个值：只有一个候选三元组：一次配对检查；若首个值为正，break 会在检查前结束。
- 全为正：首锚点就触发正数 break，返回空列表。
- 全为负：也无解，但不会触发正锚点条件；各轮因和不足而耗尽候选。
- 全为零：
[0, 0, 0, 0, 0]有十组索引组合，但只返回一次[0, 0, 0]。 - 无解：正常返回空列表，不是错误。
- 解两侧有重复：
[-2, 0, 0, 1, 2, 2]会触发两侧跳过，避免重复[-2, 0, 2]。
常见错误
- 不跳重复锚点。 默认第二个 -1 会再次找出
[-1, 0, 1]。 - 命中后只动一端。 会重复检查只能以同值再次命中的组合。两端内移，再去重。
- 已排序还依赖额外集合去重。 可以做，但增加 O(k) 存储与哈希；相邻规则已能得到规范化唯一结果。
- 忽略原地排序。 需要保留原数组顺序时，排序副本。
- 正锚点用 continue。 仍然正确，却继续处理已证明无解的锚点，break 才利用了有序性。
- 两数和直接比较 0。 两数和应比较 need；若比较 0，必须把锚点也加进和里，不能混用公式。