四数之和

暴力四重循环是 O(n⁴)，太慢。排序之后固定 i 和 j，问题就缩成「在右边找两个数，让它们的和等于 target 减去这两个固定值」，再用对撞双指针一趟扫完，整体降到 O(n³)。

第一步：排序：原数组 [1,0,-1,0,-2,2] 先排序，变成 [-2,-1,0,0,1,2]。有序之后才能用对撞双指针，也方便靠「相邻相同」跳过重复值去重。

固定 i=0 (-2), j=1 (-1)：固定前两个数：i=0 是 −2，j=1 是 −1。剩下要在右边凑出 0 减 −2 减 −1，也就是 3。左指针 l 在下标 2，右指针 r 在下标 5，当前和是 0 加 2 等于 2，比 3 小，把左指针右移换个更大的数。

i=0,j=1 · l 右移一格：左指针移到下标 3，可它也是 0，和还是 2，仍然小于 3。继续把左指针右移。

i=0,j=1 · l 再右移 · 命中：左指针移到下标 4（值 1），和等于 1 加 2 等于 3，正好凑齐！四个数 −2、−1、1、2 加起来是 0，记录第一个四元组 [−2,−1,1,2]。

i=0,j=1 · 命中后双移交叉：命中后左指针右移、右指针左移，并跳过相邻相同值。现在左指针到 5、右指针到 4，两边交叉，固定 j=1 这一轮就结束了。已收下 [−2,−1,1,2]。

固定 i=0 (-2), j=2 (0)：j 推进到下标 2（值 0），i 还是 −2。这回要凑出 0 减 −2 减 0 等于 2。左指针 l=3、右指针 r=5，和就是 0 加 2 等于 2，一上来就命中！

i=0,j=2 · 命中 [−2,0,0,2]：记录第二个四元组 [−2,0,0,2]。左右指针双移后都到下标 4，相遇，j=2 这一轮也结束。

i=0,j=3 (0) · j 层去重跳过：j 推到下标 3，值还是 0，和上一个 j 完全一样。再做一遍只会得到和刚才重复的四元组，所以直接跳过——这就是 j 层去重，少了它答案就会出现重复。

固定 i=1 (-1), j=2 (0)：i 推进到下标 1（值 −1），j=2 是 0。这次要凑出 0 减 −1 减 0 等于 1。当前和是 0 加 2 等于 2，比 1 大，这回换成右指针左移、换个更小的数。

i=1,j=2 · r 左移后命中：右指针左移到下标 4（值 1），和是 0 加 1 等于 1，命中！记录第三个四元组 [−1,0,0,1]。

i=1,j=2 · 双移交叉 · 遍历收尾：命中后双移交叉，本轮结束。再往后 i 取 0 或更大时，最小四个数的和都已经大于 0，凑不出目标，遍历到此为止。

最终结果 · 三个四元组：整趟扫描收齐三个四元组：[−2,−1,1,2]、[−2,0,0,2]、[−1,0,0,1]。这一遍把「和小了右移左指针、和大了左移右指针、命中记录、各层去重」四种情况都演了一遍。

两数之和是对撞双指针；三数之和在外面套一层固定；四数之和再套一层。规律就是：K 数之和每多一个数就多固定一层，最里面那层永远是左右指针对撞。

面试追问：三个高频追问：K 数之和怎么扩展、long 防溢出的原因、四处去重分别在哪。

迁移阶梯：把这题练到能默写后，再迁移到同类：LC15 三数之和（少一层固定）、LC16 最接近的三数之和（把相等判断改成记录最小差值）、K 数之和通用递归版。练完不妨找 AI 助教抽查你的去重逻辑，或去通关训练里实战一遍。

边界三连：边界三连：元素不足、全相同导致去重失效、大数溢出——这三种极端输入最容易让代码交出错误答案，写完先各跑一遍。