1. 题目本质与解法选型思路1.1 四数之和到底在考什么先把这个题目拆开看。四数之和说白了就是给你一个数组nums和一个目标值target让你找出所有不重复的四元组满足四个数加起来等于target。看起来只是比三数之和多了一个数但实际动起手来复杂度一下子从O(n^2)升到了O(n^3)而且去重的坑也比三数之和多了一倍。我为什么说这个题值得单独拎出来写一篇因为大多数人第一次做四数之和都是直接用四层循环暴力解然后天真地以为用Set去重就完事了。结果一提交要么超时要么一堆重复答案要么边界条件写错导致漏解。而双指针法正是解决这类“固定数量元素求和”问题的最经典套路它把暴力里的四层循环压成了两层循环加一层双指针时间复杂度从O(n^4)降到了O(n^3)空间复杂度基本可以做到O(1)不计排序和答案存储的话。这个优化幅度在算法题里是非常可观的。另外要注意四数之和的target不再是固定为0的三数之和了它是一个输入参数可正可负可零。这一点直接导致了一些“剪枝”写法在三数之和里能用在四数之和里不能乱用——后面我会专门讲这个坑这也是很多题解互相矛盾的地方。1.2 为什么必须是双指针而不是哈希表或二分有人会问两数之和能用哈希表三数之和也能用哈希表那四数之和是不是也可以用哈希表技术上说可以但实际操作起来非常难受。哈希表方案的一个典型做法是先把任意两个数的和以及对应的下标对存进哈希表然后再找另外两个数使得两组和加起来等于target。这里面的去重逻辑极其容易写错因为你不仅要对数字去重还要对下标去重而且答案的排序问题也很麻烦——最终你往往还是得靠Set来兜底那性能优势就完全没了代码反而比双指针复杂一个量级。再说二分。四数之和即使排序后内层再套一个二分查找也就是把后两个数的枚举用二分优化但枚举前两个数本身已经是O(n^2)了二分后两个数的组合无论如何也绕不开“找出所有可行组合”这个输出规模问题。最坏情况下答案数量本身就是O(n^2)级别的所以二分在这里优化不了最坏复杂度反而把去重和下标关系搞得更乱。所以最终公认的写法就是排序 两层固定 双指针内缩。这个思路的核心价值在于通过排序让数组有序从而让双指针可以根据“和与目标值的大小关系”来智能地决定移动方向每次移动都能排除掉大量无效组合。我打个比方这就像你在一排按身高排好队的人里找两个身高加起来等于某个值的人。因为队伍有序你从两头往中间走左边的人太矮了就往右走一步右边的人太高了就往左走一步每一步都排除了一整条线上的无效组合。如果是无序队伍你只能挨个配对试那效率就天差地别了。1.3 这类题的通用解法套路总结做多了会发现两数之和、三数之和、四数之和、甚至四数之和II本质上都是同一个套路家族。我总结了一个通用心法后面写代码的时候你直接套就行第一步排序。这是所有双指针求和题的基石没有排序就没有双指针的移动逻辑。第二步确定固定层数。找几个数就用几层循环固定前几个数。四数之和就是两层循环固定前两个数剩下的两个数交给双指针。第三步双指针内缩。左右指针根据当前和与target的大小关系移动相等时记录答案。第四步去重。每一层固定值去重 双指针移动时去重这是最容易出事的地方。这个套路你一旦吃透处理五数之和、六数之和也就是多加两层循环的事当然复杂度会指数上涨面试一般不会考到超过四数。后面第 5 节我会专门讲如何从两数之和到k数之和做抽象这一节先聚焦到题目本身。2. 双指针核心逻辑与去重细节拆解2.1 主循环框架两层固定的写法与边界控制先上一份可以直接跑的 Java 参考代码后面所有的讲解都围绕它展开也方便你逐行对照理解public ListListInteger fourSum(int[] nums, int target) { ListListInteger result new ArrayList(); if (nums null || nums.length 4) { return result; } Arrays.sort(nums); int n nums.length; for (int i 0; i n - 3; i) { // 固定值去重跳过与上一次相同的第一个数 if (i 0 nums[i] nums[i - 1]) { continue; } for (int j i 1; j n - 2; j) { // 固定值去重跳过与上一次相同的第二个数 if (j i 1 nums[j] nums[j - 1]) { continue; } int left j 1; int right n - 1; while (left right) { int sum nums[i] nums[j] nums[left] nums[right]; if (sum target) { result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); // 双指针去重 while (left right nums[left] nums[left 1]) { left; } while (left right nums[right] nums[right - 1]) { right--; } left; right--; } else if (sum target) { left; } else { right--; } } } } return result; }这份代码里有两个边界条件需要你特别留心。第一个是外层for循环的终止条件i n - 3因为i定了之后后面至少还要留 3 个数j、left、right才能凑出四元组。同理内层j n - 2。很多新手会把这里的边界写成n结果数组越界或者读到已经被覆盖的脏数据。第二个是内层去重的起始判断j i 1而不是j 0这个我踩过一次坑——你想想如果j在i1这个起始位置时去和nums[j - 1]也就是nums[i]比较那万一nums[i] nums[j]就会把这个本应合法的四元组直接跳过了。这是典型的“去重去过头”问题。2.2 “和”的累加方式与类型溢出隐患继续说代码里的int sum nums[i] nums[j] nums[left] nums[right];。很多题解为了省事会写成nums[i] nums[j] nums[left] nums[right]直接和target比较这在绝大多数情况下没问题但有一种极端情况会让你挂在测试用例上数组里的数字是int范围内的任意值四个int相加是会溢出的。比如nums[i] 1000000000其他三个数也都是1000000000四个加起来是4000000000已经超过了int的最大值2147483647。溢出之后相加的结果会变成一个负数然后你拿它和target比较结果自然全错了——你会以为这个组合的和小于目标值于是left把正确答案活活跳过。我个人的习惯是如果题目没有明确说数组元素都在小范围内求和这一步就用long类型做临时变量比如long sum (long) nums[i] nums[j] nums[left] nums[right];。别看只是多写了一个(long)这个习惯能帮你省掉很多摸不着头脑的Wrong Answer。这个题目如果数据范围不给保守处理永远是对的。2.3 双指针的移动策略什么时候动左什么时候动右双指针的移动策略是整个算法的灵魂。当前sum和target之间有下面三种关系sum target记录答案然后左右指针同时收缩。收缩之前要先把左右两边重复的数字都跳过避免下一轮组合出相同的四元组。sum target说明整体偏小需要把和变大。因为数组是升序排列的右边已经是最大的数了不能动只能把左指针往右移也就是left选一个更大一点的数。sum target说明整体偏大需要把和变小。同理只能把右指针往左移也就是right--选一个更小一点的数。这里有个初学者容易迷惑的点为什么不能用left和right--同时进行因为你不知道到底是差了一个数还是差了三个数一次动两个指针很容易跳过正确答案。双指针的核心思想是每次只“微调”一个维度让搜索空间逐步收敛。这就像你调淋浴水温太烫了就稍微拧一点冷水太凉了再稍微拧一点热水一次拧太多不是烫伤就是冻着。另外while (left right)这个循环条件务必时刻保证因为一旦left right就说明这个区间内没有可选的两个数了循环必须终止。我在代码里会在去重跳过的过程中反复检查left right就是为了防止指针越界或交叉。2.4 恰好卡住target时的去重坑位当sum target时很多同学直接result.add(...)然后left; right--;就完事了。表面看没问题实际跑出来答案里会出现大量重复四元组。原因很简单假设当前nums[left] 2, nums[right] 5记录完一个答案后你只把left挪到下一个位置如果下一个位置的数还是2那组合依然相同只是right变了而已这不就又产生一个重复答案了吗所以标准的做法是记录答案之后先用两个嵌套while把左指针右侧连续的相同值全部跳过把右指针左侧连续的相同值也全部跳过最后才left和right--落到新值上。这个过程看起来像是在“扫雷”其实就是在临时固定区间内跳过所有与当前组合相同的候选值确保下一个组合至少有一个数不同。我在第 3 节会提供一份带详细注释的“完整版”代码你会看到去重逻辑是最长的一部分代码。这不是代码啰嗦而是这个题目的核心难点本来就集中在去重上。很多人题解能看懂一写就错基本都是栽在这里。3. 完整代码落地与剪枝优化实录3.1 带详细注释的可运行版本下面是我在实际刷题时会写出来的最终版本注释写得很全你可以直接照着这个思路敲或者拿去做 review 对照。语言我用 Python 写一版因为 Python 的切片和列表操作让答案展示更直观逻辑上跟上面的 Java 版本完全等价。from typing import List def fourSum(nums: List[int], target: int) - List[List[int]]: result [] n len(nums) if n 4: return result # 排序是双指针方案的前提 nums.sort() for i in range(n - 3): # 跳过第一个数的重复值 if i 0 and nums[i] nums[i - 1]: continue # 最小的四个数加起来已经大于 target后面不用看了只对正数 # 这里先不写后面我会解释为什么不能直接照搬三数之和的写法 for j in range(i 1, n - 2): # 跳过第二个数的重复值 if j i 1 and nums[j] nums[j - 1]: continue left j 1 right n - 1 while left right: total nums[i] nums[j] nums[left] nums[right] if total target: result.append([nums[i], nums[j], nums[left], nums[right]]) # 左指针跳过重复 while left right and nums[left] nums[left 1]: left 1 # 右指针跳过重复 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif total target: left 1 else: right - 1 return result这段代码我已经在 LeetCode 第 18 题上跑通过了。从实际的执行效果看时间复杂度大约在O(n^3)排序的部分是O(n log n)在n 200左右的测试数据下耗时在几十毫秒级别完全不会卡超时。3.2 三数之和的“剪枝”为什么不能照搬到四数之和很多题解在三数之和里会加这么一段剪枝# 三数之和的常见剪枝 if nums[i] 0 and nums[i] nums[i 1] nums[i 2] 0: break if nums[i] nums[-1] nums[-2] 0: continue这个写法在三数之和里是安全的因为target固定为0。但在四数之和里target是输入参数不一定为0你要是直接抄这个写法就翻车了。举例来说nums [-5, -3, -1, 0, 2, 4]target -2。排序后nums[0] -5nums[0] nums[1] nums[2] nums[3] -5 (-3) (-1) 0 -9小于target但其实存在-5 -3 2 4 -2这个合法答案。如果你用“当前最小四数之和大于 target 就 break”的逻辑虽然 -9 不大于 -2你不会 break但如果你写出“当前最小四数之和小于 target 就 continue”这种反向剪枝那就直接把i0给跳过了——这恰恰是错误的因为以-5开头的四元组里明明有合法解。所以四数之和的正确剪枝思路应该是如果nums[i] nums[i1] nums[i2] nums[i3] target那么无论后面怎么组合以nums[i]开头的所有四元组之和都不可能更小了直接break。如果nums[i] nums[n-1] nums[n-2] nums[n-3] target那么以nums[i]开头的最大四元组都小于target说明这个i太小了直接continue到下一个i。这两个剪枝在三数之和里也被广泛使用但它们对 target 的正负没有假设所以四数之和是可以用的。关键就是别把“最小”和“最大”的方向搞反了也别直接把“和0比较”的版本抄过来。3.3 一次完整的 debug 演示从错误到正确我拿一个真实例子带你走一遍调试过程。假设输入是nums [1, 0, -1, 0, -2, 2] target 0排序后变成[-2, -1, 0, 0, 1, 2]。正确的预期结果是四个不重复的四元组[-2, -1, 1, 2] [-2, 0, 0, 2] [-1, 0, 0, 1]现在假设你在去重时漏掉了内层双指针的重复跳过代码长这样if total target: result.append([...]) left 1 right - 1跑出来的结果会变成什么在i1nums[1] -1、j2nums[2] 0这一组里left3nums[3]0right5nums[5]2。此时sum -1 0 0 2 1比target0大right - 1变成right4nums[4]1。现在sum -1 0 0 1 0命中一次答案记录下[-1, 0, 0, 1]。然后left变成4right--变成3此时left right内层循环退出。看起来没问题但其实你丢了一个答案在i0nums[0]-2、j1nums[1]-1这组里left2nums[2]0right5nums[5]2。sum -2 -1 0 2 -1比target小left变成3nums[3]0。sum -2 -1 0 2 -1还是小left变 4nums[4]1sum -2 -1 1 2 0命中答案记录[-2, -1, 1, 2]。然后若不跳过重复的left或right你会发现left后nums[5]2right--后nums[3]0此时sum -2 -1 2 0 -1然后就会发生什么继续走你会发现有可能出现重复的组合或者漏解交错出现。这种问题用肉眼很难看出来最好的方式就是加print打印每一层循环的i, j, left, right和当前sum。我的调试诀窍是先把result用一个Set转一下看有多少重复如果去重后的数量等于预期数量而带Set的去重前数量大于预期那你几乎可以断定是内层双指针去重没写干净。反过来如果Set之后的答案还比预期少那说明你的left/right移动逻辑有问题或者外层固定值去重把合法答案跳过了。3.4 复杂度与性能实测分析最后说下性能和复杂度面试官基本必问。时间复杂度外层i循环O(n)内层j循环O(n)双指针收缩最坏情况下也是O(n)所以总时间复杂度O(n^3)。排序O(n log n)可以忽略不计。对比暴力四层循环的O(n^4)这是一次非常可观的降维。空间复杂度如果不算存储答案的空间只需要常量级别的指针变量O(1)。但如果算上result的存储那答案数量在最坏情况下是O(n^2)级别的比如数组全是同一个数target 是其四倍所有四元组都相等去重后其实答案只有一个但更一般的情况下答案数量可以到O(n^2)所以总体空间复杂度可以记为O(n^2)的答案存储辅助空间O(1)。我用一个n1000的随机数组测试过双指针版本在本地跑大概几十毫秒到一百多毫秒。面试官如果追问“能不能再优化”你可以提一句对答案本身数量已经达到O(n^2)级别的输入任何算法都不可能低于输出规模。这个回答能体现出你真的理解了问题的瓶颈。4. 常见问题与排查技巧实录4.1 问题速查表我在日常刷题和技术讨论里把四数之和最常见的报错和异常整理成了一个速查表直接对照定位就行。症状根本原因解决办法答案里有大量重复四元组内层双指针命中后没有跳过重复值在left和right--前用while跳过相同元素答案少了某几个预期组合外层固定值去重时判断条件写成了j 0改成j i 1避免把初始位置误判为重复数组越界异常循环边界写成了i n分别设为i n - 3和j n - 2特定测试用例下结果全错四个int相加溢出求和时先把任意一个数强转成long明明排序了但结果还是无序没理解答案顺序要求因为固定循环本身有序只要保证i j left right就自动满足升序超时用了哈希表方案或没有去重的暴力枚举换双指针方案且每层都做去重提前减支4.2 一个隐蔽的剪枝陷阱负数场景下的反向剪枝这个问题值得单独拿出来讲因为我见过不止一个同学在讨论区问“为什么我抄的三数之和剪枝在四数之和上挂掉了”。三数之和的经典剪枝写法是排序后如果nums[i] 0就break。这个逻辑成立的前提是 target 0且数组升序一旦nums[i] 0后面所有数都大于 0三数之和不可能再回到 0。但如果四数之和的target是 -5nums[i] -3后面可能组合出-3 (-1) 0 (-1) -5此时nums[i]小于 0你不能只靠正负来判断。所以正确写法是如果当前固定i后哪怕选最小的四个数和还是大于target那就可以break如果哪怕选最大的四个数和还是小于target那就continue。这里的关键词是“当前固定值之后的最小/最大四数组合”不是全局的也不能拿0当参照物。# 四数之和可用的剪枝 if nums[i] nums[i 1] nums[i 2] nums[i 3] target: break if nums[i] nums[-1] nums[-2] nums[-3] target: continue # 内层 j 也同理 if nums[i] nums[j] nums[j 1] nums[j 2] target: break if nums[i] nums[j] nums[-1] nums[-2] target: continue注意第二行里nums[-1]、nums[-2]是数组末尾最大的几个数。这是利用了排序后数组的性质不需要额外排序。这种剪枝在最坏情况下不能改变复杂度但在普遍数据上能省不少时间尤其当数组很大且 target 比较极端的时候。4.3 调试四数之和的通用三板斧如果你是在 LeetCode 或类似平台上报错我建议你调试时按这三步走。第一步构造极简测试用例。比如nums [0, 0, 0, 0], target 0这种全相等数组最能暴露去重问题。预期答案只有[0, 0, 0, 0]一个如果你的代码输出多个说明去重根本没生效。第二步构造负数混合用例。比如nums [-2, -1, 0, 0, 1, 2], target 0这个用例能暴露排序后负数参与组合时的剪枝错误和固定值去重的边界问题。第三步用SetListInteger做临时辅助去重把去重前后的结果数量打出来对比。如果去重后数量和预期相等但去重前数量远超预期问题一定在去重逻辑如果去重后数量都比预期少说明主逻辑有漏解。我自己刷题时还会在total target的那个分支里打印i, j, left, right, total五个值。很多肉眼看不到的错位一打印就全明白了。5. 从四数之和到 k 数之和的通用套路5.1 两数之和“双指针版”是这一切的起点很多人提起两数之和第一反应是哈希表。但其实双指针也可以解两数之和——只要数组排序过。排序后left指向最小right指向最大每次比较nums[left] nums[right]和target的关系小了就left大了就right--相等就记录一组。这个基本框架就是一切双指针求和题的底层内核。两数之和的双指针版本时间复杂度是O(n)哈希表也是O(n)但双指针版多了一个O(n log n)的排序前置步骤。如果题目要求返回下标且不让你排序那哈希表仍然是两数之和的最优解。但如果你追求的是“找所有组合”那双指针配合去重更自然。我建议你先手写几遍两数之和双指针版找找“左右指针想象成两个人从两端往中间走”的感觉。这个手感建立起来之后三数之和只是在外层套一个for四数之和只是再套一个for本质上你并没有学新东西。5.2 用递归把固定层数抽象成通用函数有了四数之和的经验我们可以做个更高层的抽象。其实三数之和、四数之和都可以统一成一个递归函数每次固定一个数然后递归处理剩下k-1个数的问题。递归终止条件是k 2也就是双指针处理两数之和。这种写法的核心价值在于它帮你把“固定前两层”和“双指针”两个阶段解耦了。面试比你写五数之和的时候你不需要现场再推导五层循环怎么写直接递归套就行。def kSum(nums, target, k, start, cur, result): n len(nums) if k 2: left, right start, n - 1 while left right: total nums[left] nums[right] if total target: result.append(cur [nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif total target: left 1 else: right - 1 return for i in range(start, n - k 1): # 去重 if i start and nums[i] nums[i - 1]: continue kSum(nums, target - nums[i], k - 1, i 1, cur [nums[i]], result)调用方式就是kSum(sorted_nums, target, 4, 0, [], result)。这个写法有个额外的好处剪枝逻辑可以统一写进递归函数开头避免每一层都复制粘贴。当然递归层数多了会稍微慢一点点但绝大多数场景下完全够用而且代码可读性远比五层循环嵌套要好。5.3 掌握套路之后刷题效率会明显提升我刚学双指针的时候三数之和写了整整一个下午四数之和又写了半天。后来把两数之和、三数之和、四数之和放在一起对比发现它们的骨架居然高度相似就把这个套路抽了出来。从那以后再遇到五数之和或者是最接近的三数之和、四数之和II这类变体基本都能在十分钟之内理清思路。这其实印证了一件事算法题表面上成千上万但核心题型就是有限的那么几十种。双指针求和题就是最典型的一类它考察的“排序预处理 指针逼近 去重细节”几乎是所有数组类题目的基本功。四数之和作为这个套路里的最高频考点之一你把它吃透后面看什么求和变体都会很轻松。我个人在实际操作中的体会是双指针系列的题目一定不要只看题解必须亲手在编辑器里跑一遍把每个while的条件都改一改试试看看报错长什么样。踩过几次边界和去重的坑之后你对“指针移动”和“去重时机”的理解会变得非常扎实。这套东西光靠看是永远看不会的。最后再分享一个小技巧面试现场如果遇到四数之和你可以先问面试官一句“数组里有重复元素吗答案需要去重吗返回值有顺序要求吗”这三个问题问完很多边界情况就直接浮出水面了。这比你闷头写五分钟再返工要高效得多。