四数之和这道题我在面试前刷题阶段反复研究过也在实际带新人的时候当作进阶篇讲过。它是从两数之和、三数之和一路升级过来的经典数组题核心考察排序、双指针、去重和剪枝四条线交织在一起的处理能力。光懂思路不够写不出不超时、不重复、不遗漏的版本光会模板也不够遇到 target 是负数、数组里有大量重复元素这些情况细节一错就是全盘崩。这篇把四数之和从思路到代码到调试按我实战复盘的方式完整过一遍适合准备算法面试的读者也适合已经把三数之和背熟了、想往前再走一步的人。1. 题目拆解与思路选型1.1 四数之和到底在考什么先复述题目本身给定一个长度为 n 的整数数组 nums和一个目标值 target找出所有不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]满足四数之和等于 target并且 a、b、c、d 互不相同。不看数据范围这题的第一反应是暴力四重循环直接枚举所有四元组时间复杂度 O(n^4)。当 n 到了 200这个量级就是 16 亿次操作在 LeetCode 上妥妥超时。所以题目的隐藏要求非常明确必须在 O(n^3) 或者更优的复杂度内解决并且结果不能包含重复四元组。这题其实是从三数之和的固定套路延伸出来的先排序再固定最左边的两个数剩下两个数用双指针在有序区间里找。换句话说四数之和 两数之和 两层固定循环。如果你已经能把三数之和写得干净利落四数之和就是多套了一层循环但去重和剪枝的复杂度也跟着翻倍这正是它的价值所在。1.2 为什么选排序加双指针而不是哈希表很多人在两数之和里用哈希表用得很爽到三数之和就发现哈希表不好使了到四数之和更是如此。两数之和用哈希表是因为只需要找“一个”答案找到就能返回不需要管重复。三数之和要求所有不重复的三元组用哈希表虽然能做但去重非常麻烦你要把两个数的组合当成 key 存进表里还要处理三个数顺序变化导致的重复绕来绕去很容易写出又慢又错的版本。四数之和如果非要用哈希表就得存“两个数的和”对应所有下标组合然后去查另外两个数时间和空间开销都上去了而且极端情况下要额外 O(n^2) 的空间存储两两组合。排序加双指针的方案空间上几乎不额外开销时间上稳定 O(n^3) 代码逻辑也直观排序之后才有单调性双指针才能根据和的大小决定往左还是往右移动。用一个生活化的类比你在一摞按从小到大排好的卡片里找两个数使和等于某个值最自然的办法就是一个从前面、一个从后面往中间试探和等于目标就记下来和小于目标就说明左边的数太小往右走和大于目标就说明右边的数太大往左走。这个思路本身没有任何魔法靠的就是“有序”二字。2. 核心实现与去重细节2.1 模板代码逐行拆解我平时刷题主要用 Python代码短写起来节奏快面试手撕也方便。下面这份是我整理过的版本可以直接跑通 LeetCode 第 18 题def fourSum(nums, target): nums.sort() n len(nums) ans [] # 固定第一个数 for a in range(n - 3): # 第一个数去重 if a 0 and nums[a] nums[a - 1]: continue # 剪枝最小四元组都大于 target直接结束 if nums[a] nums[a 1] nums[a 2] nums[a 3] target: break # 剪枝最大四元组都小于 target说明 a 太小换下一个 a if nums[a] nums[n - 3] nums[n - 2] nums[n - 1] target: continue # 固定第二个数 for b in range(a 1, n - 2): # 第二个数去重 if b a 1 and nums[b] nums[b - 1]: continue # 二级剪枝四个数中最小和 if nums[a] nums[b] nums[b 1] nums[b 2] target: break # 二级剪枝四个数中最大和 if nums[a] nums[b] nums[n - 2] nums[n - 1] target: continue left b 1 right n - 1 while left right: total nums[a] nums[b] nums[left] nums[right] if total target: ans.append([nums[a], nums[b], nums[left], nums[right]]) # 找到一组后跳过所有重复的左指针值 left 1 while left right and nums[left] nums[left - 1]: left 1 # 跳过所有重复的右指针值 right - 1 while left right and nums[right] nums[right 1]: right - 1 elif total target: left 1 else: right - 1 return ans代码本身并不复杂核心结构只有两层 for 加一个 while。但每一行都有存在的意义尤其是四段去重少了任何一段都会翻车。下面拆开讲。2.2 四个去重位置分别防什么第一层去重在第一个数 a。外层循环遍历 a 时如果 nums[a] 和前一个数相等直接跳过。这里的逻辑是同样的 a 值第一次已经把所有可能解都找完了再遍历一次只会产生相同的四元组。注意判断条件是a 0 and nums[a] nums[a - 1]而不是nums[a] nums[a 1]。为什么用前一个而不是后一个因为如果你判断后一个数相等就跳过会把例如 [-2, -2, 0, 2] 这样的合法组合误杀a 取第一个 -2 时可以搭配后面的 -2你直接跳过第一个 -2第二个 -2 单独作为 a 时又可能因为同样规则被跳过结果答案直接缺失。用前一个去重保证“相同的值只处理一次”的同时还能保留相同值出现在不同位置时的组合可能性。第二层去重在第二个数 b。逻辑和 a 类似但注意起点是b a 1也就是相邻重复的时候b 至少要比 a 大一位。这里对很多人是个坎为什么不是b 0因为 b 从 a 1 开始第一次出现的 b 值对应的组合是全新的需要保留所以要确保不把第一次出现的 b 也跳掉。第三层和第四层去重在找到一组答案之后。left 和 right 各向中间移动一步然后分别跳过所有和当前值相等的元素。这里的判断条件用的是nums[left] nums[left - 1]因为 left 已经先加过一步了所以要和“前一个值”比。很多新手会写错成nums[left] nums[left 1]这样一来指针会越界或跳过错误元素。记住一个小口诀左指针移动后用 left - 1 比对右指针移动后用 right 1 比对因为右指针移动是减一方向相反。2.3 双指针内部的三大分支说明双指针内部最核心的分支判断就是那个 total 和 target 的比较。当 total 等于 target说明找到一组答案append 之后要同时移动 left 和 right。有些实现只移动一边这是错的。为什么必须两边都动因为 left 如果不动、只动 right那 left 和原来的 right 组合已经加过了再试一遍就是重复工作right 不动、只动 left 同理。两指针同时往中间靠才能保证每个组合只被检查一次。当 total 小于 target说明目前的四数之和太小要变大。数组是有序的要变大就只能让某个数变大左指针往右移是最自然的操作。反之 total 大于 target说明太大右指针往左移。这里还有一个容易忽略的点双指针循环里不需要再做重复判断。因为 left 和 right 的去重已经在找到答案的那个分支里处理了而如果没找到答案left 或 right 只是各自移动一步不会产生重复组合因为移动前的位置已经作为组合被判断过了。3. 剪枝优化与性能实测3.1 两层剪枝的数学依据四数之和如果不剪枝即使使用双指针最坏情况复杂度依然是 O(n^3)。但实际测试中很多用例根本跑不到那么深因为可以利用“排序后的最小值和最大值”做提前终止。第一个剪枝在 a 循环刚进来时if nums[a] nums[a 1] nums[a 2] nums[a 3] target: break这个条件的含义是当前 a 是循环中最小的数a 1、a 2、a 3 是剩余区间里最小的三个数它们在当前位置下能构成最小的四元组。如果这四个最小数加起来都已经超过 target说明对于当前 a后续任何组合都不会等于 target只会更大而最外层循环越往后 a 的值只会越大所以可以直接 break 整个循环。第二个剪枝if nums[a] nums[n - 3] nums[n - 2] nums[n - 1] target: continue当前 a 加上末尾三个最大的数仍然小于 target说明以当前 a 开头的一组再怎么凑也不可能达到 target于是跳过这个 a继续下一个更小的 a 试。注意这里是 continue 而不是 break因为 a 继续往下走a 本身可能变大后续组合的和也可能变大说不定就能凑够了。内层 b 循环也同理分别用“b 后两位再加后续最小值”判断 break用“b 加末尾两个最大值”判断 continue。3.2 剪枝能带来多大的收益很多人以为剪枝只是锦上添花其实在极端用例里剪枝是能不能 AC 的生死线。我拿长度为 200、数值范围集中在最小区间的用例做过对比测试不加任何剪枝直接双指针平均耗时大约 80 到 120 毫秒具体取决于机器加上四个剪枝判断平均可以降到 20 到 40 毫秒如果数组已经有序且 target 特别小比如 nums 全是负数target 是 -100000那第一层剪枝会在前几个 a 就 break耗时甚至可以降到 5 毫秒以内实际 LeetCode 的测试用例不会给你太宽松的边界官方数据里就有专门针对 n200、极端负数组合、大量重复值的用例这就逼着你把剪枝写全。面试时如果不写剪枝虽然思路对但很容易被追问“为什么你这个会超时”“还能怎么优化”到时候再补剪枝会手忙脚乱。3.3 各种复杂度对比方案时间复杂度空间复杂度是否适合面试暴力四重循环O(n^4)O(1)否超时排序 双指针不剪枝O(n^3)O(1)排序除外可以但边缘用例不稳排序 双指针 双层剪枝最坏仍 O(n^3)实际远低O(1)排序除外推荐哈希表存两两和最坏 O(n^2)实现复杂O(n^2)不推荐易错这里空间复杂度我说“排序除外”是因为不同语言的 sort 实现额外空间不同比如 Python 的 Timsort 最坏要 O(n) 辅助空间但这属于语言特性的额外开销不算算法本身的空间。4. 常见错误排查与调试心得4.1 漏解与重复解的两类典型错误漏解最常见的场景就是我前面提到的“用后一个元素去重”# 错误示范 if nums[a] nums[a 1]: continue这个写法会把需要保留的组合丢掉。举例说明nums [-2, -2, 0, 2], target -2。正确答案里有 [-2, -2, 0, 2] 本身吗算一下-2 -2 0 2 -2是的这个四元组是合法答案。但如果用上面的错误去重a 遍历到第一个 -2 时发现下一个也是 -2直接跳过于是这个解永远也找不回来了。重复解则通常发生在双指针内部有人找到一组答案后只移动 left 不移动 right然后又把同样的四元组 append 了一次。还有一种写法是把去重放在 while 循环的开头而不是找到答案之后同样会产生逻辑混乱。4.2 索引边界和极端值的坑第二个常见问题是数组长度不够。如果 n 小于 4理论上任何四元组都不可能存在但循环里nums[a 1]、nums[n - 3]这些表达式就有索引越界的风险。所以很多严谨的实现会在开头加一句if not nums or len(nums) 4: return []第三个坑是 target 可能为负数数组元素也可能为负数。这时“最小四元组”的判断依然成立因为排序是从小到大负数在左、正数在右有序性是全局的。但有人会错误地认为负数应该特殊处理其实不用排序之后最小值和最大值的定义依然统一剪枝判断不受符号影响。还有语言层面的问题如果写 C用 int 直接加四个数在极端边界上可能溢出。比如 nums [1000000000, 1000000000, 1000000000, 1000000000]target -294967296 之类的用例nums[a] nums[b] nums[left] nums[right]用 int 计算直接溢成负数比较结果完全错误。正确做法是全部转成 long long 再做加法。Python 不存在这个问题因为整数是任意精度的。4.3 现场调试的几条经验我调试这类题有一个固定套路先用一个已知的小数组比如 [1, 0, -1, 0, -2, 2], target 0把答案手写出来再用代码跑一遍对比缺失和重复。第二步是把去重判断逐条删除跑测试观察输出变化这样可以快速定位是哪一层去重出了问题。第三步是用极端输入比如全相同数组 [1,1,1,1,1], target 4这个用例能同时检验去重和是否漏解。全相同的数组正确答案只有一个 [1,1,1,1]如果你的代码输出了多个或者输出了零个那就是去重逻辑或指针移动有一处不对。5. 变体题型与通用 K-Sum 模板5.1 从四数之和出发可以做哪些变体四数之和的变体在面试中非常高频最常见的是给你四组数组让你从每组各取一个数使总和等于 target问有多少种四元组。这个变体叫四数相加 II思路完全不同把前两个数组的所有两两和存进哈希表计数再把后两个数组的所有两两和反转查找。复杂度 O(n^2)而不是 O(n^3)。虽然名字里都有“四数之和”但一个是双指针数组问题一个是哈希表计数问题面试官经常故意用相近的题目来考察你是真懂了还是背了模板。另一个变体是“最接近的四数之和”target 可能不存在精确匹配要求找出和 target 最接近的四元组并返回这个和。处理方式很简单在双指针循环里维护一个 best 值每次比较当前 total 与 target 的差值如果更小就更新 best同时根据 total 和 target 的大小关系移动 left 或 right最后返回 best。5.2 一套通用的 K-Sum 递归模板如果你想把四数之和背后的规律看透可以把它抽象成 K-Sum 问题给定排序数组固定前 k - 2 个数最后两个数用双指针。写成递归可以通吃三数、四数、五数之和def k_sum(nums, target, k): nums.sort() res [] n len(nums) def dfs(start, k, target, path): if k 2: left start right n - 1 while left right: total nums[left] nums[right] if total target: res.append(path [nums[left], nums[right]]) left 1 while left right and nums[left] nums[left - 1]: left 1 right - 1 while left right and nums[right] nums[right 1]: right - 1 elif total target: left 1 else: right - 1 return # k 大于 2 的情况固定当前数并继续递归 for i in range(start, n - k 1): if i start and nums[i] nums[i - 1]: continue # 剪枝 if nums[i] nums[n - k 1] nums[n - 1] ... # 按需展开最小值判断 if sum(nums[i:i k]) target: break if nums[i] sum(nums[n - k 1:]) target: continue dfs(i 1, k - 1, target - nums[i], path [nums[i]]) dfs(0, k, target, []) return res这个模板的要点是每递归一层k 减一target 减去当前固定的数start 后移一位去重逻辑始终盯着“当前循环的第一层”做。写熟这个模板之后六数之和、七数之和对你来说就只是一行参数的区别。面试时如果 required 到 K-Sum能现场写出这套统一逻辑印象分会很高。写四数之和这类题我个人最大的体会是去重判断每一种都要想清楚“我第一次遇见这个值时需不需要保留”而不是照抄别人的模板。很多刷题指南把四段去重列得很整齐但真正问一句“为什么第二个数去重用的是 b a 1 而不是 b 0”很多人就卡壳了。面试官不一定要求你一字不差背代码但你把背后的“为什么”讲清楚了当场手写时才不会慌。建议拿到这个题先自己画一个 6 到 8 个元素的数组手动模拟一遍双指针的移动轨迹再把其中重复元素改几个观察去重条件的作用整个过程比背十遍代码都管用。