四数之和这道题刷LeetCode的人基本都绕不过去。它看起来只是在三数之和后面加了一个数但真到自己动手写的时候很多人会发现完全不是那么回事——去重逻辑绕晕、int溢出踩坑、剪枝不到位导致超时各种问题接踵而至。我最早写这道题时直接用四层循环暴力解结果是正确性没问题一旦数据量上来就当场TLE。后来老老实实把双指针的思路吃透才明白这道题真正想考察的不是“你会不会套模板”而是你对排序、指针收缩、去重边界和剪枝优化的综合理解。这篇文章我会把四数之和从思路到实现完整讲一遍重点放在为什么要这么做、双指针为什么能降复杂度、去重和剪枝的具体细节以及我在调试过程中踩过的坑。无论你是刚开始刷双指针题目的新手还是已经写过但总在边界条件上栽跟头的进阶选手这篇文章都值得你花十分钟读透。1. 从暴力枚举到双指针收缩四数之和的思路是怎么长出来的1.1 暴力解法的天花板在哪里题目描述很简单给你一个由整数组成的数组 nums和一个目标值 target找出所有不重复的四元组[nums[a], nums[b], nums[c], nums[d]]满足四个数之和等于 target并且每个四元组内部按升序排列。最直白的思路就是四层循环枚举 a、b、c、d 四个下标检查nums[a] nums[b] nums[c] nums[d] target满足就把结果存下来。四层循环的时间复杂度是 O(n⁴)在力扣的测试数据下n 稍微过百就非常吃力更别说去重逻辑还要用集合或者排序来额外处理。暴力解法其实还有一个很隐蔽的问题去重成本高。即使你用Set去重存储和哈希的开销也会拖慢整个程序。所以这道题如果以暴力方式写大概率会超时这也是它被归为重点题目的原因——它逼着你寻找更优的解法。1.2 双指针为什么能把复杂度降一维双指针的核心思想本质上来自“有序数组”带来的性质。一个有序数组里如果你把两个指针分别放在区间两端通过比较当前和与目标值的大小可以确定性地知道下一步该移动左指针还是右指针从而在 O(n) 时间内完成两数之和的查找。这个过程不需要额外哈希表也不需要回溯。放到四数之和这道题里思路就变得清楚了先排序然后用两层循环固定前两个数剩下两个数用双指针在区间内寻找。这样四层循环就降成了两层循环加一层线性扫描整体复杂度从 O(n⁴) 降到了 O(n³)。排序本身是 O(n log n)相比 O(n³) 可以忽略不计。我打个比方帮助理解假设你在一列升序排列的数字里找两个数凑成一个固定值最笨的办法是把所有组合都试一遍但如果利用“当前和太小就说明左边的数不够大把左指针右移当前和太大就说明右边的数太大把右指针左移”这个规律每一步你都能排除掉一大片不可能的组合这就是双指针省时间的本质。2. 排序、双层固定、双指针收缩核心实现逐行拆解2.1 排序是双指针能成立的前提很多人写这道题时第一步就忽略了排序的重要性直接开始枚举。不排序双指针根本无法工作因为只有数组有序你才能根据和的大小判断该移动哪个指针。所以代码的第一步一定是nums.sort()这一步做完后面所有逻辑的地基才算打好了。Python 里 sorted 会返回新列表nums.sort()是原地排序省内存建议直接原地排序。排序还有一个附加好处它让“去重”变得非常简单。相同的数在排序后会挤到一起你只需要在循环时跳过和前一个位置相同的元素就能保证同一个值的下标不会重复枚举。这一点后面会详细展开。2.2 外层两重循环固定住前两个数排序之后我们用两个变量 i 和 j 分别代表第一个数和第二个数的下标。i 从 0 遍历到 n-4因为后面至少要留三个位置给 j、left、rightj 从 i1 遍历到 n-3。这一步就是“固定两个数把四数之和转化为两数之和”的核心。外层两个循环里需要做两件事一是跳过重复值二是做初步剪枝。跳过重复的逻辑是if i 0 and nums[i] nums[i-1]: continue为什么是nums[i] nums[i-1]而不是nums[i] nums[i1]因为前者表示“当前这个值已经作为第一个数处理过了”后者在 i 还没往后走时就把当前的重复值跳过了会导致你漏掉正确结果。同理j 的循环也要跳过重复值if j i 1 and nums[j] nums[j-1]: continue这里尤其要注意 j 的去重起点是i 1因为 j 的第一个位置无论和前一个数相不相等都要处理不能一上来就跳过。2.3 内层双指针移动规则与命中处理固定好 i 和 j 之后剩下两个数的查找就是经典的双指针逻辑。设 left j 1right n - 1然后计算当前四数之和 totaltotal nums[i] nums[j] nums[left] nums[right]比较 total 和 target如果 total 等于 target说明找到了一组答案。此时记录结果然后移动 left 和 right 跳过所有重复值最后再各自向中间收缩一步。如果 total 小于 target说明四数之和太小需要更大的数让 left 右移。如果 total 大于 target说明四数之和太大需要更小的数让 right 左移。为什么要同时跳过重复值因为如果不跳left 移动到下一个相同数值时和 right 的组合依然等于 target你会把完全相同的四元组重复加入结果这就是去重的第三处关键点。命中 target 后两个指针必须同时收缩。这一点很多初学者想不通为什么左指针右移之后右指针不能保持不变呢因为当前的总和已经等于 target如果只移动一边新的和一定不等于 target数组有序且已跳过重复值所以两边都必须动才能进入新的搜索区间。完整的核心代码段如下def fourSum(nums, target): nums.sort() n len(nums) res [] for i in range(n - 3): if i 0 and nums[i] nums[i-1]: continue for j in range(i 1, n - 2): if j i 1 and nums[j] nums[j-1]: continue left, right j 1, n - 1 while left right: total nums[i] nums[j] nums[left] nums[right] if total target: res.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 res这段代码已经能 AC 大部分测试数据了。但如果你想在数据量很大的情况下依然保持不错的性能就得看下面这节剪枝优化。3. 去重与剪枝从超时到AC的分水岭3.1 三处关键去重一处都不能省四数之和的去重一共有三处位置缺一不可。第一处是 i 层面的去重。如果不加数组[2, 2, 2, 2, 2]这种用例会输出大量重复四元组。第二处是 j 层面的去重起点必须是i 1理由前面已经说过。第三处是 left 和 right 层面的去重也就是命中 target 之后连续跳过重复值。第三处有一个容易被忽略的细节跳完重复后还需要最后执行left 1和right - 1。很多人写完两个 while 循环后就直接进入下一轮 while结果 left 还是指向最后一个重复元素right 也还是指向最后一个重复元素下一轮比较时又得到一个等于 target 的和导致死循环。我在实际调试中见过太多这样的死循环了建议你在写的时候把“跳过重复”和“指针收缩”这两步分开写清楚不要合并成一个步骤可读性和正确性都能提升。3.2 两个方向的剪枝优化剪枝是四数之和里最能体现水平的部分。排序之后数组有序我们可以利用“当前情况下能得到的最小和、最大和”来做提前终止判断减少不必要的循环。第一个剪枝如果当前固定的 nums[i] 加上其后最小的三个数nums[i1]、nums[i2]、nums[i3]已经大于 target那说明 i 再往后取只会更大直接 break 整个外层循环。因为数组升序i 越往后nums[i] 越大大最小的四个数之和只会越来越大后面的情况不可能满足条件。第二个剪枝如果 nums[i] 加上数组最后三个最大的数nums[n-1]、nums[n-2]、nums[n-3]仍然小于 target说明 i 这个位置作为第一个数太小了就算加上最大的三个数都不够于是直接 continue跳到下一个 i。同样的剪枝逻辑在内层 j 的循环里也要写一遍。把 j 的剪枝代码补上整体效率能提升 20% 到 30%for i in range(n - 3): if i 0 and nums[i] nums[i-1]: continue # 第一层剪枝当前最小的四数之和大于 target直接跳出 if nums[i] nums[i1] nums[i2] nums[i3] target: break # 第二层剪枝当前最大的四数之和小于 targeti 换下一个 if nums[i] nums[n-1] nums[n-2] nums[n-3] target: continue for j in range(i 1, n - 2): if j i 1 and nums[j] nums[j-1]: continue # 内层剪枝 if nums[i] nums[j] nums[j1] nums[j2] target: break if nums[i] nums[j] nums[n-1] nums[n-2] target: continue ...要注意target 为负数时这两个剪枝依然成立因为排序后的数组依然满足“最小四数之和递增”的性质剪枝逻辑不依赖 target 的正负。4. 溢出、空数组、临界值调试四数之和的实战记录4.1 int溢出的经典翻车现场如果你用的是 C 或 Java四数之和有一个特别经典的坑整数溢出。力扣的测试数据里有一个用例是nums [1000000000, 1000000000, 1000000000, 1000000000]target 也是很大的数。四个 10 亿相加等于 40 亿已经超过了 int 类型的上限 2147483647于是计算结果会变成负数导致比较逻辑完全混乱。解法有两个思路把四个数逐个强制转换为 long long 再相加避免中间过程溢出在循环内部用 long long 变量承接四个数的和再与 target 比较。第一次遇到这个问题时我花了大半天时间才定位到是溢出因为逻辑查了很多遍都没错最后打印中间量才发现问题。这里提醒你只要目标值和你数组中的数可能接近 int 上限任何涉及四数相加的地方都要先把类型放大。Python 没有这个问题因为它的整数是任意精度的但 C 和 Java 一定要小心。4.2 边界条件与测试用例设计除了溢出还有几个边界条件在实际写代码时很容易漏掉数组长度小于 4直接返回空数组数组元素全为负数时target 也可能是负数不能默认 target 为正数组中大量重复元素时去重逻辑是否真的生效left 和 right 在移动过程中会不会出现下标越界。我的习惯是写完代码后先用几组经典用例做回归测试。最基本的用例包括nums [1, 0, -1, 0, -2, 2], target 0期望输出[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]再跑一个全相同的数组再跑一个数组长度刚好为 4 的用例最后跑一个目标值非常极端的用例。这套组合拳打下来基本能覆盖绝大多数边界问题。调试的时候我还建议你在关键循环里打印i, j, left, right, total这几个值。很多人觉得打印日志很麻烦但遇到死循环或者结果缺失时这一步往往能一分钟定位问题。尤其是去重逻辑报错的场景打印出当前比较的下标你一眼就能看出是不是漏了“跳过重复值”那一步。5. 从四数之和到K数之和双指针思路的举一反三5.1 KSum问题的通用框架四数之和掌握了之后你会发现三数之和、五数之和、K数之和本质上都是一个套路。把 KSum 写成一个递归函数固定一个数然后在剩余数组中找 K-1 数之和当 K 等于 2 时使用双指针在线性时间内查找。这个框架可以适配任意 K 值面试时能说出来是很大的加分项。递归框架的伪代码大概是这样的def kSum(nums, target, k, start): res [] if k 2: left, right start, len(nums) - 1 while left right: if nums[left] nums[right] target: res.append([nums[left], nums[right]]) while left right and nums[left] nums[left1]: left 1 while left right and nums[right] nums[right-1]: right - 1 left 1 right - 1 elif nums[left] nums[right] target: left 1 else: right - 1 return res for i in range(start, len(nums) - k 1): if i start and nums[i] nums[i-1]: continue for sub in kSum(nums, target - nums[i], k - 1, i 1): res.append([nums[i]] sub) return res递归版本的时间复杂度是 O(n^(k-1))优势是代码简短统一适合 K 不固定的场景缺点是递归调用有一定开销K 很小的时候不如直接写嵌套循环清晰。四数之和这种 K 4 的题目面试官更想看的是你能不能高效地写出两层循环加双指针递归方案可以作为扩展话题提一嘴。5.2 双指针题型的适用边界双指针并不是万能的它最大的前提是“数组有序”或者“问题能通过有序性来排除搜索范围”。常见适用场景有这么几类两数之和有序数组版三数之和、四数之和盛最多水的容器接雨水删除有序数组中的重复项。这些题目的共同特征是都利用了对撞指针在有序区间内快速收缩达到 O(n) 或 O(n²) 级别的复杂度。遇到无序数组时要么先排序要么考虑哈希表方案两者各有优劣。排序会改变元素顺序如果题目要求返回下标且答案依赖原始下标就不能直接排序要另想思路。我从自己的刷题经验来看四数之和真正难住人的不是思路本身而是去重和边界。很多人知道双指针这个方法但写出来总差一点。建议你动手之前先在纸上把 i、j、left、right 四个指针的可能位置画一遍把三个去重位置标注出来再动笔写代码一次写对的概率会高很多。如果一次没过也别急着看题解把报错的用例打印出来对照上面的检查清单往往能自己找出问题。