★ FEATURED ARTICLE 1. 四数之和的题目定位与核心解题模型LeetCode第18题“四数之和”是双指针类问题的经典进阶题。凡是刷过题库的人基本都走过这样一条路线先做“两数之和”再做“三数之和”然后撞上这道“四数之和”。它考察的已经不只是哈希表的用法而是更底层的双指针思维、去重处理和剪枝优化能力。说白了这一题能顺利AC说明你对双指针体系的掌握已经进入了一个比较稳的状态。题目本身描述并不复杂给你一个由n个整数组成的数组nums以及一个目标值target请你找出所有不重复的四元组[nums[a], nums[b], nums[c], nums[d]]使得四个数相加等于target。注意两点一是四元组内部可以按任意顺序组织但结果集里不能出现重复的四元组二是答案中每个四元组里的元素是按值去重不是按下标去重。这道题解决的核心问题其实是“在无序数组里高效筛选特定组合”的问题。暴力解法当然能写四层循环枚举所有组合时间复杂度O(n^4)n一上了500基本就跑不动了。实际面试和工程场景里这种复杂度完全不可接受。所以我们需要一个接近O(n^3)的方案。为什么O(n^3)是合理的因为在排序的基础上两数之和可以用双指针做到O(n)外层嵌套两层固定循环后总复杂度就是O(n^3)n1000时大概10亿次操作配合剪枝后还能压缩不少已经是常规赛道上比较优的解法了。我没记错的话很多人在三数之和那题里习惯用“固定一个数 双指针”的模板到了四数之和就又懵了多了一层循环该怎么去重该在哪里剪枝target是负数时还能不能沿用三数之和的“第一个数大于target就break”的经验这些细节都直接决定你能不能写出无bug版本。这篇文章主要就是把这些点掰开揉碎讲清楚适合刚刷完三数之和、准备跨到四数之和的读者也适合准备面试前集中复盘双指针技巧的开发者。2. 从两数之和到三数之和再到四数之和的规律拆解2.1 为什么先排序是必须的一步很多第一次做这题的人会惯性思维“两数之和不是用哈希表解的吗四数之和是不是也能用哈希表”确实能但哈希表方案要应对重复四元组去重的话需要大量额外判断代码量和出错概率都直线上升。我个人的建议是凡是题目要求返回“所有不重复的组合”而不是返回下标排序就是压倒性优势的选择。排序给问题带来的核心改变是数组变成有序的双指针的移动就有了方向性。left指针向右移动和会变大right指针向左移动和会变小。基于这个单调性我们才能用O(n)的时间在一个有序区间里找出所有和为特定值的两数组合。如果不排序双指针的移动方向没有任何数学依据整个方案就崩塌了。排序的代价是O(n log n)这个成本在n不太离谱的情况下完全值得。而且排序还在去重环节帮了大忙相同的值会排在一起我们只需要判断“当前这个数是否和前一个数相等”就能轻松跳过相同值的重复枚举比哈希表方案里遍历结果集去重不知道高到哪里去了。2.2 双指针在四数之和里的角色定位先把整体框架说清楚。四数之和 固定两个数 双指针找剩下两个数。外层用i枚举第一个数内层用j枚举第二个数然后用left和right在j右侧的区间里双指针寻找满足条件的两个数。为什么left要从j1开始而不是从0开始如果从0开始会造成组合重复比如固定了i和j之后left扫到i或j本身那就变成同一个数被用了两次既不符合题意也会产生大量重复计算。这是新手特别容易踩的坑。这里还有一个数学上的小观察数组排序之后如果前两个数已经固定那么剩下两个数越小四数之和越小剩下两个数越大四数之和越大。双指针就是利用这个单调性质从两端向中间逼近。当四数之和小于target时说明需要更大的数left右移大于target时说明需要更小的数right左移。整个过程就像用一个可以伸缩的夹子去夹住target非常直观。2.3 三数之和的模板为什么不能直接套用三数之和的经典写法里外层固定i内层left从i1开始right从n-1开始双指针相向移动。很多文章会教你一个经验“如果nums[i] 0就直接break因为后面都是正数怎么加都不可能是0”。到了四数之和题目给的target是任意整数可能是负数。这个经验就不灵了。举个例子nums [-10, -5, 0, 1, 2]target -14。第一个数取-10虽然-10大于target吗不大于。但如果你用“nums[i] target就break”这个错误的剪枝逻辑第一个数取-5的时候-5 -14你会直接break从而漏掉[-5, -10, 1, 2]这个合法答案当然这里的组合顺序会由其他循环负责我只是说明这个剪枝是错的。所以四数之和不能照搬三数之和里“第一个数大于0就break”的经验必须换成更严谨的剪枝条件后面的章节会详细展开。3. 双指针方案的完整设计与细节推敲3.1 固定前两个数的循环框架整个算法的骨架是两层for循环外层i从0到n-1内层j从i1到n-1。每次固定i和j之后问题就退化为在nums[j1]到nums[n-1]这个有序区间中找到两个数使得它们的和等于target - nums[i] - nums[j]。这就是一个标准的两数之和双指针问题。写成代码框架就是这样ListListInteger res new ArrayList(); Arrays.sort(nums); int n nums.length; for (int i 0; i n - 3; i) { // 剪枝和去重 for (int j i 1; j n - 2; j) { // 剪枝和去重 int left j 1; int right n - 1; while (left right) { long sum (long) nums[i] nums[j] nums[left] nums[right]; if (sum target) { res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); // 去重移动 left; right--; } else if (sum target) { left; } else { right--; } } } } return res;这里有几个细节你需要品一下。第一i的最大值是n-4因为至少要留出j、left、right三个位置同理j的最大值是n-3。循环边界写错是这类题目最常见的bug之一少写一个边界就可能数组越界。第二四个数之和用int存可能会溢出如果nums里的数很大比如接近Integer.MAX_VALUE四个数相加会直接变成负数判断逻辑就全乱了。所以我在代码里用long强转。3.2 去重逻辑的正确姿势去重是四数之和里最烦人但也最重要的部分。结果集要求四元组不重复这里的“重复”指的是值的组合重复比如[1, 1, 2, 2]和[1, 2, 1, 2]算同一个四元组。由于我们固定了i j left right的顺序组合天然有序所以去重只需要保证同一个位置上的值不要重复枚举。具体来说外层i循环里如果nums[i] nums[i-1]直接跳过。这里要注意是跟i-1比不是跟i1比。跟i1比会误伤合法组合比如nums [1, 1, 2, 3, 4, 5, 6]target 12组合[1, 1, 2, 3, 6]需要用到两个1如果用“nums[i] nums[i1]就跳过”的逻辑第一个1固定时就被跳过了直接丢解。正确的做法是只在“当前这个值已经被完整枚举过一轮”之后才跳过。内层j同理当j i 1且nums[j] nums[j-1]时跳过。left和right的移动也一样找到一个合法组合后left要向右跳过所有相同的值right要向左跳过所有相同的值然后再继续下一轮查找。不这样做的话同一个组合会被重复添加到结果集多次。3.3 剪枝优化的两个关键判断剪枝能让代码从“超时边缘”变成“稳过”尤其当数组长度很大时。四数之和里有两个非常实用的剪枝条件。第一个剪枝如果当前固定的i之下最小的四个数之和都大于target那么后续更大的i值只会让最小值组合的和更大可以直接break。所谓最小的四个数就是nums[i] nums[i1] nums[i2] nums[i3]。这是一个强剪枝因为它可以直接结束外层循环。第二个剪枝如果当前固定的i之下最大的四个数之和都小于target说明当前i值太小了再怎么取也凑不到target可以直接continue让i继续右移。所谓最大的四个数就是nums[i] nums[n-3] nums[n-2] nums[n-1]。这两个剪枝呈犄角之势一个管上界一个管下界配合起来能把大量无效枚举直接跳过。内层j循环里也可以做类似的剪枝判断固定i和j后最小的两个nums[j] nums[left] ... 其实就是nums[j] nums[j1] nums[j2] nums[i]和最大的两个nums[j] nums[n-2] nums[n-1] nums[i]是否越界。实际操作中我见过很多人在剪枝这里吃到亏把break和continue搞混或者漏掉j层的剪枝导致结果正确但性能不够。剪枝不是可选项面对n等于1000甚至2000的用例没有剪枝基本就是等着超时。4. 代码实现、复杂度分析与实战场复盘4.1 完整的Java参考实现把上面所有细节整合起来我贴一份我实际用过的完整实现加了必要的注释public ListListInteger fourSum(int[] nums, int target) { ListListInteger res new ArrayList(); if (nums null || nums.length 4) return res; Arrays.sort(nums); int n nums.length; for (int i 0; i n - 3; i) { // 去重当前值已经枚举过一轮 if (i 0 nums[i] nums[i - 1]) continue; // 剪枝最小四数之和超过target后续只会更大直接结束 if ((long) nums[i] nums[i 1] nums[i 2] nums[i 3] target) break; // 剪枝最大四数之和小于target当前i过小继续下一轮 if ((long) nums[i] nums[n - 3] nums[n - 2] nums[n - 1] target) continue; for (int j i 1; j n - 2; j) { if (j i 1 nums[j] nums[j - 1]) continue; if ((long) nums[i] nums[j] nums[j 1] nums[j 2] target) break; if ((long) nums[i] nums[j] nums[n - 2] nums[n - 1] target) continue; int left j 1; int right n - 1; while (left right) { long sum (long) nums[i] nums[j] nums[left] nums[right]; if (sum target) { res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); left; right--; // 跳过重复值防止重复组合 while (left right nums[left] nums[left - 1]) left; while (left right nums[right] nums[right 1]) right--; } else if (sum target) { left; } else { right--; } } } } return res; }这段代码是我反复调整过很多次的版本能同时处理重复值、负数target和溢出情况。你不需要原样照抄但每个判断条件最好都搞清楚为什么存在。4.2 为什么每一处判断都值得仔细琢磨先说去重那几行。i的去重条件是“如果i大于0且nums[i]等于nums[i-1]就跳过”。这个条件背后的逻辑是当i0时没有前一个元素所以必须用i 0做保护当nums[i]等于nums[i-1]时说明当前这个值和上一个枚举过的值一样再用它做固定点生成的四元组集合和上一次完全重合纯属浪费。但是要注意我没有在i0时跳过连续相同的值比如nums [0, 0, 0, 0, 0]target0i0时不能跳过因为这是第一个合法枚举机会唯一的结果[0,0,0,0]必须靠它产生。再讲left和right的跳过逻辑。找到一个合法组合后left和right--各移动一步然后分别跳过与移动后位置相同的值。为什么移动一步之后还要再跳因为如果不跳比如nums[left]移动后仍然等于原来的值下一轮while循环又会算出相同的合法组合并重复加入结果集。这个细节漏掉的话代码跑出来会看到一堆重复四元组结果集大小完全不对。剪枝那几行的long强转也值得说一说。虽然理论上排序后的数组里四个数相加可能超过int范围但实际刷题平台给的测试用例往往不会极端到溢出。不过作为工程习惯写long转义并没有性能损失还能杜绝偶发的溢出bug。我见过有人在面试现场因为四个int相加溢出导致判断错误花了大半个小时排查这种低级失误完全可以用一个强转避免。4.3 复杂度分析的实践含义排序的时间是O(n log n)三层循环i、j、双指针每层最多跑n次所以时间复杂度是O(n log n n^3)简化成O(n^3)。空间复杂度主要看结果集存储最坏情况下所有四元组都是答案需要O(C(n,4))也就是O(n^4)级别的空间但这个不算在算法辅助空间里题目一般也不care。实际跑起来剪枝对这个O(n^3)的常数影响非常大。同样是n1000裸的三层循环大概要跑10亿次加法再加上去重判断很容易超时加了剪枝之后大部分情况下i和j的循环都会被提前终止或跳过实际运算量能降到几百万级别。这也是为什么同一个算法有人AC稳过有人总在最后一个用例上报超时的核心原因。5. 实战中遇到的典型问题与排查手册5.1 结果集出现重复四元组这个问题的根源基本都是去重逻辑写漏了。最常见的两种一是忘了在left和right移动后跳过重复值导致同一组合被多次加入二是内层j去重时把条件写成if (nums[j] nums[j1]) continue导致连续相同值中最后一个被跳过但前面的值重复枚举。排查方法是打印每个满足条件的四元组肉眼观察重复规律然后定位是哪个固定层出了问题。还有一个小众但很坑的情况当target为负数且数组里有大量负数时i层的“nums[i] target就break”这种三数之和遗留经验会直接导致丢解。我上面已经举例过了负数的世界里四个更小的负数相加可能等于一个更负的target所以不能用正数场景的直观判断。5.2 输出顺序导致的结果对比失败有些平台在比对结果时要求每个四元组内部从小到大排序且四元组之间按字典序排序。如果直接照搬我上面的代码因为i和j都是从左往右固定的生成的组合天然有序一般不需要额外处理。但如果你用哈希表方案生成组合时顺序会比较随机最后就得加一步排序才能通过。我建议你提交前先自己构造几个用例验证一下输出是否符合预期。比如nums [1, 0, -1, 0, -2, 2]target 0预期应该输出[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]。这个用例几乎所有四数之和的题解都会引用你可以拿它当第一个自测用例。5.3 循环边界越界异常外层i最多到n-4内层j最多到n-3这个边界我反复提过了。很多人会把外层循环写成i n然后在内部访问nums[i3]时越界。还有一个隐蔽问题当n 4时直接返回空列表这个条件判断必须放在排序之前还是之后都行但必须要有。我有一次就是忘了判空和长度不足结果空数组直接进入循环白屏报错。5.4 剪枝条件误伤合法答案剪枝本身是性能优化但如果写错条件就会变成“错误答案加速器”。我在代码里用的两个剪枝其数学依据很简单排序后对于固定的i最小的四个数的和是nums[i] nums[i1] nums[i2] nums[i3]如果连这个和都大于target那i再往右只会更大因为nums[i]增大且后面三个也至少不会变小所以直接break最大的四个数的和是nums[i] nums[n-3] nums[n-2] nums[n-1]如果连这个和都小于target那i再往右更大也没用直接continue。这两个条件都不会漏解可以放心用。但有一种情况你要特别小心如果target是负数最小的四个数之和可能小于target吗可能。所以剪枝条件不能写成nums[i] nums[i1] nums[i2] nums[i3] target后就默认“后面全是正数”你要么听我的用long强转要么至少意识到负数场景下这个判断依然成立——它成立的根源不是“后面都是正数”而是“排序后数组单调不减”。6. 从四数之和到N数之和面试考法与能力迁移6.1 一个模板解决所有K数之和四数之和刷完之后很多人会问那五数之和、六数之和怎么办其实这类题目有一个统一的递归模板。核心思路不变排序后用递归固定第一个数然后在剩余区间里递归求解(K-1)数之和K2时用双指针收尾。这个模板我在面试中用过也看着别人用过只要理解了去重和剪枝的通用规则从四数跳到K数只是加一层递归的事。递归版本的伪代码大概是这样的public ListListInteger kSum(int[] nums, int target, int k, int start) { ListListInteger res new ArrayList(); if (k 2) { // 双指针查找两数之和 } else { for (int i start; i nums.length - k 1; i) { // 去重 剪枝 ListListInteger sub kSum(nums, target - nums[i], k - 1, i 1); // 把nums[i]加入每个子结果 } } return res; }但这里有个效率问题递归每层都创建新列表内存消耗比迭代版大。所以LeetCode上四数之和还是推荐用迭代解法K数之和的变体题比如力扣上的某些扩展题才需要上递归版。6.2 面试官真正想考察的东西四数之和这道题在面试里出现的频率不算特别高但非常有代表性。面试官让你做这道题大概率不是真的关心你会不会找四元组而是想看你能否在掌握了双指针、去重、剪枝这些核心技巧之后把它们组合起来解决一个复杂度更高的问题。你的思路是否清晰、能不能主动分析时间复杂度、愿不愿意考虑边界场景比如溢出、负数target这些才是评分点。我建议你刷这道题之前先确保自己能一口气写出无bug的三数之和。三数之和是四数之和的降级版四数之和是三数之和的自然延伸。如果三数之和还要debug半小时那四数之和大概率会更痛苦。6.3 这道题在实际业务里的影子你可能会问这种纯算法题跟实际开发有什么关系说实话直接找一个四数之和的场景不太容易但它的底层能力其实天天都在用。比如推荐系统里要选出若干物品凑到某个预算约束下最优组合比如金融系统里要在一组票券中找出组合满足对账条件再比如游戏的合成系统要检查玩家手上的资源能否合出目标道具。这些场景本质都是“在集合中搜索满足特定组合约束的项”背后的排序、双指针、剪枝思想完全通用。我印象很深的一次经历是处理一个库存匹配的需求有一批订单要合并发货发货重量要接近某个目标值当时我第一反应就是把这题的双指针思路搬过去。虽然实际工程里还掺杂了各种业务约束但核心的“有序区间内双指针逼近目标”的思路帮了大忙。7. 几个让我印象深刻的调试瞬间刷算法的乐趣之一就是那些让你拍大腿的瞬间。我刚开始写四数之和的时候在剪枝那里栽过一次大跟头。当时我把break写到了j循环里面结果i固定之后j只跑了一次循环就整个退出了答案少了一大片。我盯着代码看了半天满脑子都是“语法没错啊”完全没意识到是循环结构写错了。后来我把每个循环里的index值通过打印日志输出才看到j根本没有遍历完。还有一次是去重逻辑的经典错误我用while (left right nums[left] nums[left 1]) left;来代替找到答案后的去重结果是怎么跑都丢解。原因很简单left移动前nums[left]和nums[left1]相同移动后我跳过了这个值但同时也可能把一个还没用来匹配的组合跳过了。正确姿势是先正常移动left和right各一步再去重跳过连续相同值。顺序差一步结果天壤之别。再讲一个负数的坑。LeetCode的示例里有nums [-1, -1, 0, 1, 2]target -2之类的负数用例。如果你用三数之和的经验判断“第一个数大于target就break”那第一个数取0的时候0 -2就break了直接丢掉所有可能有0参与的组合。我在这个坑里浪费过整整一个晚上最后是在纸上手算两个用例才琢磨明白。这些debug经历让我养成了一个习惯写完代码不要急着提交先手动构造几个极端用例自测。负数、全零、全是相同值、数组长度刚好为4、target很大或很小这几个用例一跑大部分隐藏bug都会现形。你把这个习惯保持下来刷题效率和代码自信度都会明显提升。四数之和这道题初看是“三数之和的版本升级”但实际写起来涉及到的细节比想象中多得多。把这一题吃透再去刷其他双指针题比如盛最多水的容器、接雨水心态上会轻松很多。如果你刷这道题时卡住了别硬磕太久回到三数之和把基础模板复习一遍再回来往往就通了。我个人是这么过来的相信对你也一样。
阅读完成 · 觉得有帮助？
