三数之和3Sum这道题几乎是我见过的刷题群里讨论热度最高的一道算法题。它不像动态规划那样劝退新手也不像图论题那样在整个算法体系里偏门它正好卡在一个“人人都能听懂解法但很少有人能一次写对”的位置。很多人能背出排序加双指针的模板但一旦被追问“为什么跳过重复元素时要用 while 而不是 if”“两个指针移动的先后顺序能不能换”“数组里有负数时剪枝条件怎么写”瞬间就露馅了。这篇文章我想把这道题从暴力解法到双指针的完整推导过程拆开讲清楚顺带分享我在面试现场和实际编码中踩过的那些坑以及它背后一套可以举一反三的思维模式。这道题适合所有正在准备算法面试的人也适合那些工作中偶尔要和数组、去重、组合条件打交道的开发人员。三数之和表面上是求三元组实际上考察的是三个基本功排序后的有序性如何被你利用、双指针收缩区间如何避免重复计算、以及如何处理“去重”这种看起来简单却暗藏细节的逻辑。把这三点吃透你收获的不只是考试分数还有一种处理有序数组问题的通用直觉。1. 三数之和到底在考什么1.1 问题定义与典型场景先明确题目本身。给你一个包含 n 个整数的数组 nums判断数组中是否存在三个元素 a、b、c使得 a b c 0你需要返回所有和为 0 且不重复的三元组。几个关键约束三元组内部顺序不重要但三元组之间不能重复也就是说 [ -1, 0, 1 ] 和 [ 0, 1, -1 ] 是同一种答案另外如果数组中存在多个相同的数值它们可以被组合进同一个三元组但同一个索引位置的元素不能重复使用。举个例子nums [-1, 0, 1, 2, -1, -4]答案集是 [ [-1, -1, 2] ] 和 [ [-1, 0, 1] ]注意这里有两个 -1它们刚好可以组成一个合法三元组而不会被视为重复使用。我一开始看到这道题时第一反应是“这有什么好考的三个循环不就完了”但如果数组长度是 3000三重循环就是 270 亿次运算任何在线评测系统都会直接超时。这才是这道题最核心的矛盾解法要快同时要保证结果不重不漏。考察的不是你会不会写循环而是你能不能理解“为什么有序数组可以用双指针把复杂度压一个量级”。很多人在 LeetCode 上提交时遇到的问题是要么结果集里出现了重复三元组要么漏掉了一些合法组合要么死循环这三个问题背后都指向同一个根源——去重逻辑没有放在正确的位置。1.2 为什么这道题在面试里这么高频三数之和在面试中出镜率极高我参加过的技术面试里至少遇到过三次类似的题目。面试官喜欢它的原因很简单它覆盖面广又能分层考察。基础差的候选人可能只能给出暴力解法中等水平的候选人能给出排序加双指针优秀的候选人能当场分析剪枝条件、内存占用和极端情况的处理。而且这道题从暴力到最优解的思维跨度很大非常适合用来判断一个人的算法直觉不需要候选人背复杂的数据结构却能通过追问不断压出深度。时至今日我仍然觉得刷三数之和比刷十道背诵型动态规划题更有价值。它背后是一整套“有序化处理”的思维方式先把数组排序让无序问题变得有结构可循再用左右指针动态逼近目标值最后通过指针跳过重复值来实现去重。这种思路在后续处理三数之和的变种时比如最接近目标值的三数之和、四数之和甚至 N 数之和都能复用。面试官一旦确认你能举一反三这个考点就完全变成了加分项而不是及格线。2. 从暴力解法到双指针的思维跃迁2.1 暴力三重循环和它的复杂度瓶颈暴力解法是每个新手接触这道题的第一站。你写三个循环枚举所有 i j k 的组合检查三元组的和是否为零再手动去重。去重怎么做大多数人会把三元组排序后放进 Set或者在收集结果时检查一下是否已经存在。这个过程代码量不小而且性能很差。三重循环的时间复杂度是 O(n^3)当 n 为 1000 时已经达到十亿级别实测下来绝对超时。但暴力解法的意义不在于性能而在于建立问题模型。你真正需要的是在 n^3 个候选中找到满足条件的那些去重只是后处理。当你盯着暴力枚举的过程看会发现大量的重复计算固定一个元素 i 后内部两重循环其实是在无序子数组中寻找两个数它们的和等于 -nums[i]。这个视角一旦建立你就意识到真正需要解决的其实是“两数之和”问题只不过这次是在排序后的数组里用双指针做。从暴力到双指针核心思想并不复杂暴力之所以慢是因为它在做无差别的枚举没有利用数组的任何结构信息。排序是一种天然的预处理手段它不改变问题的解集却把所有元素组织成了线性有序的结构。有序数组让“区间收缩”成为可能左指针向右移动会让和变大右指针向左移动会让和变小于是你可以根据当前和与目标值的比较结果只移动必要的那一侧指针。这样固定一个元素后剩下的两数查找从 O(n^2) 降到了 O(n)整体复杂度从 O(n^3) 降到了 O(n^2)。这个“排序降低维度”的思路是双指针题型的灵魂。2.2 排序加双指针最经典的主流通解整个解法的框架分三步排序、固定一个数、用双指针找两数之和。我先描述宏观流程再拆细节。第一步把数组从小到大排序。第二步从左到右遍历数组把当前元素固定为 a作为三元组中最小或第一个元素。第三步在当前位置右侧的区间里设置两个指针left 从 a 的下一位开始right 从数组尾部开始计算当前三元组的和。如果和小于 0说明整体偏小left 右移如果和大于 0说明整体偏大right 左移如果和等于 0记录这个三元组然后同时收缩两个指针继续寻找其他组合。这里有一个极其关键的认知为什么固定一个数之后剩下的两数之和必须在 a 的右侧寻找而不是在整个数组中寻找因为如果允许 left 越过 a 的位置你会产生重复的三元组比如固定了 a1在右侧找到 b2、c-3之后固定 a2又在左侧找到了 b1、c-3两个三元组其实是同一组数字只是排列顺序不同。所以从左到右固定 a每次搜索区间严格限定在其右侧天然避免了顺序导致的重复。这个设计比事后去重优雅得多也是双指针写法能够高效去重的根本原因。2.3 去重细节为什么跳过重复元素如此关键我认为三数之和最容易被忽视的地方就是去重。很多代码能跑通但结果集里有大量重复项就是因为去重位置不对。去重有两个关键位置一是外层循环固定 a 时如果当前遍历到的元素和前一个元素相同说明这个固定值已经处理过了继续走只会得到重复三元组必须跳过。这里用的是 if 跳过而不是 while 后移后继续执行因为比较的对象是 a 和前一个 a只需判断一次即可。二是内层找到和为 0 的组合时left 和 right 都要跳过重复值。一个常见的错误是只判断 nums[left] nums[left 1] 或者 nums[right] nums[right - 1] 但只移动一次那样还是可能落入重复组合。正确做法是连续跳过所有相邻重复值让指针直接落到一个新的数值上。我举个例子帮你理解。数组是 [-2, 0, 0, 2, 2]。固定 a -2 时区间内有 0 和 2。left 先指向第一个 0right 指向最后一个 2三者和为 0记录 [-2, 0, 2]。此时如果只把 left 右移一位、right 左移一位left 还是 0right 还是 2三者和仍然是 0又记录了一个重复的 [-2, 0, 2]。这就是为什么在记录完一组答案后要让指针跳过所有与当前值重复的位置然后再各收缩一位进入新的数值区间。很多自测明明通过了简单用例却在数组大量重复时失败的场景基本都栽在这里。3. 代码实现与细节打磨3.1 一份可直接上手的 Python 与 Java 实现先看 Python 实现这是我平时刷题最常用的版本def three_sum(nums): nums.sort() n len(nums) result [] for i in range(n - 2): # 剪枝数组已排序当前元素大于0则后面元素都大于0三数之和必大于0 if nums[i] 0: break # 跳过固定的重复值 if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: left 1 elif total 0: right - 1 else: result.append([nums[i], 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 return result再看 Java 版本结构完全一致只是用了 Java 的集合操作public ListListInteger threeSum(int[] nums) { ListListInteger res new ArrayList(); Arrays.sort(nums); int n nums.length; for (int i 0; i n - 2; i) { if (nums[i] 0) break; if (i 0 nums[i] nums[i - 1]) continue; int left i 1; int right n - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { left; } else if (sum 0) { right--; } else { res.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--; } } } return res; }两边代码逻辑一致你完全可以根据自己的主力语言迁移。我个人的习惯是在本地把这两个版本都跑一遍因为 Python 的处理更直观适合推导边界条件而 Java 的读者群更广适合在面试中手写时用。注意两个细节外层循环的终止条件是 i n - 2因为后面至少要给 left 和 right 各留一个位置否则会越界内层 while 条件始终要带 left right防止指针交错后还在计算和。3.2 边界条件与易错点清单我整理了一份自己在实际刷题和面试中踩过坑的易错点清单可以对照着自检。易错点具体表现正确做法忘记剪枝固定元素大于 0 仍进入内层循环数组有序nums[i] 0 时直接 break外层去重时机不对写成与后一个元素比较导致漏解应与前一个元素 nums[i - 1] 比较内层去重少了 while只跳过一次重复值仍会收集重复三元组连续跳过所有相邻重复值后再收缩指针指针收缩顺序混乱在没跳过重复值时就 left 和 right--先跳过重复后同时收缩指针固定数小于零但剪枝不生效没理解有序数组才能剪枝剪枝依赖于排序顺序必须先排序三元组顺序不一致没加“从固定位右侧搜索”的约束固定 a 后 left 从 i 1 开始数组长度为边界n 小于 3 时返回空列表先判断或让 range 自然不执行这里我想特别展开“外层去重时机”这个点。假设数组是 [-1, -1, 0, 1]外层第一次循环固定第一个 -1能找到 [-1, 0, 1]。第二次循环 fixed 到第二个 -1 时如果你写成 if i 0 and nums[i] nums[i 1] 比较的是当前元素和后一个元素当后一个元素与当前元素相同但要继续跳过时你可能会在第一个 -1 处就被误判跳过导致漏掉 [-1, 0, 1]。正确写法是 nums[i] nums[i - 1]因为你要跳过的对象是“已经作为固定位处理过的值”而不是“尚未处理的值”。这个顺序问题几乎每个新手都会踩一遍写错时还不容易察觉。3.3 复杂度分析与性能实测时间复杂度方面排序是 O(n log n)外层固定元素是 O(n)内层双指针最多移动 n 次所以双指针部分整体是 O(n^2)。最终时间复杂度为 O(n^2)。空间复杂度取决于排序算法实现如果是原地排序比如 Java 默认的 DualPivotQuicksort额外空间是 O(log n) 到 O(n)如果忽略排序栈空间可以认为辅助空间是 O(1)。对比暴力三重循环的 O(n^3)在 n 3000 时理论耗时从亿级降到了百万级差距非常明显。我在本地实测过一组随机生成的数组包含 5000 个重复度比较高的整数。暴力三重循环跑了超过 90 秒还没结束而排序加双指针版本稳定在 0.4 到 0.7 秒之间。这组数据里大量重复元素正是去重逻辑的试金石官方测试用例也经常会塞入这样的数据专门考察你没注意到的去重漏洞。如果你发现自己的代码在小数组上输出正确但提交后出现 Time Limit Exceeded多半是去重不够狠导致结果集过大内存和时间同时拉满。4. 进阶变种与扩展思考4.1 最接近的三数之和掌握了三数之和以后你应该顺手做一下它的变种题目最接近目标值的三数之和。问题描述是给定一个数组和一个目标值 target要求找出三个数使它们的和最接近 target并返回三个数的和。两题的框架高度相似唯一的区别是不用再收集所有解也不用处理三元组级去重只需要维护一个最小差值。实现时排序后固定一个数内部双指针收缩每次都计算当前和与 target 的差值绝对值如果比当前记录更小则更新答案。当当前和小于 target 时 left 右移大于 target 时 right 左移。一个重要的剪枝是如果某次当前和直接等于 target直接返回因为差值已经是 0不可能更小了。这个题目让我理解到双指针不只用于“精确寻找目标值”也适用于“逼近目标值”它本质上是一个在单调有序区间上的高效搜索策略。4.2 四数之和与 N-Sum 问题的推广学会了三数之和四数之和就是套娃。四数之和的核心思路是在外层再多套一层循环固定两个数让内部双指针在剩余区间内搜索两数之和等于剩余目标值的组合。时间复杂度从 O(n^2) 变成 O(n^3)但对有序数组的依赖不变。去重逻辑同样要出现在每一层循环里外层固定第一个数时跳过重复固定第二个数时跳过重复内层找到目标后跳过左右指针的重复。我在实际推导 N 数之和时发现一个规律N-Sum 问题本质上都是两数之和的递归化表达很多时候面试官会让你思考“如果传入的是四个数你怎么改”。答案是每多一个维度就多一层固定值的循环外层循环的层数与 N-2 成正比。这种递归思想我已经在多个算法题目中受益比如组合求和、子集生成等。吃透三数之和的双指针结构再往四数之和扩展时几乎不用背任何新东西只需要把去重规则层层复制到位。4.3 哈希表解法与空间换时间有人会问双指针是不是唯一的解法其实哈希表也能做只是通常不是最优。思路是固定两个数然后在哈希表里查询第三个数是否存在于剩余区间中。它的时间复杂度也是 O(n^2)但空间复杂度上升到 O(n)而且去重逻辑更麻烦因为哈希表是无序的你很难只用一个方向搜索来避免重复三元组。实测下来哈希表方案在多数数据集上不如双指针方案稳定特别是数组较大且重复较多时哈希表扩容带来的内存压力会和去重复杂度叠加。我理解哈希表方案的价值在于它是一个思维拓展而不是推荐的生产级方案。如果你在面试中被追问“双指针以外的解法”你可以提哈希表指出它的时间复杂度和双指针相同但空间更差还需要额外处理重复项。这个回答能展示你对时间空间权衡的完整认知比单纯说一句“双指针更好”有说服力得多。但实际写代码时我依然会选择双指针因为它的去重边界在有序数组的框架下极其清晰。5. 常见问题与排查技巧实录5.1 面试现场的高频追问面试官在面这道题时几乎不会满足于让你默写一遍代码他们通常会在你写完代码后抛出几个刁钻的问题。下面这些是我亲身遇到过的追问和自己的应对思路。第一个追问排序加双指针的解法是否稳定这个问题实际上在问去重逻辑是否会漏解。你要先解释为什么外层循环只在前一个元素相同时跳过而不是在下一个元素相同时跳过说明原因在于跳过太晚会导致重复三元组跳过太早则会让合法三元组被误杀。第二个追问如果数组中有大量负数剪枝条件是否仍然成立答案是成立。剪枝依赖于数组有序而不是取决于元素符号。当前固定位大于 0 时右侧所有数都大于等于当前值因此三者之和必然大于 0可以安全 break。注意这里说的是大于 0 而不是大于 target在三数之和中 target 固定为 0。第三个追问是很多候选人的死穴如果 nums 中包含极大整数比如 Java 中 int 溢出怎么办我在一次现场面试中就漏掉了这一点。标准双指针写法里 sum 直接使用 int 保存三个正数相加可能溢出为负数导致判断方向错误。解决方式是使用 long 保存 sum或者先将三个数中较大的值转成 long 再相加。你可以在代码里把 sum 定义为 long在比较时强转。实际工程里不一定会遇到这么大的数组值但面试官抛出这个问题时你要能立刻反应过来并给出修正方案。5.2 实际工程中的场景延伸你可能觉得三数之和这种纯算法题现实中哪会用到。其实不然。我在做数据处理需求时多次遇到过“在数据集中寻找组合满足某种约束”的场景比如在价格列表里找三件商品总价恰好落在某个目标区间内或者在推荐系统中对用户行为特征向量做组合筛选。这些需求往往不需要精确搜索全部三元组但双指针的核心思想能被迁移成“有序特征空间上的交集搜索”策略。还有一类延伸是在内存受限环境下处理流式数据。比如你有一个不断追加的时间序列数组每次新数据到达后需要查询是否存在三步移动窗口满足某种和式约束。这时你不可能每来一个数据就跑一遍完整的三数之和而是要维护有序结构并用窗口双指针增量更新。虽然工程实现复杂度远高于刷题但底层逻辑仍然是排序、单调区间、指针收缩这三板斧。所以我一直认为三数之和这类题目不该只当作考试题去背它训练的是对有序数组的敏感度这种敏感度在许多真实问题处理中都会悄悄发挥作用。最后再说一个实用的本地调试技巧当你写完三数之和的解法后先用一个含大量重复元素的小数组做测试例如 [0, 0, 0, 0, 0, 0, 0]期望答案是 [[0, 0, 0]] 且只有一条。再测试包含负数和正数交错的数组比如 [-5, -5, 1, 2, 3, 4, 10]观察是否会漏掉 [-5, 2, 3]。然后把 nums 换成反序数组确认排序逻辑正确。这些测试用例我至今保留在本地测试脚本里每次调试类似去重题目都会复用省下了大量排错时间。踩过几次坑之后我开始明白三数之和的真正难点从来不在于写出循环而在于你在思考去重与边界时是否足够严谨。 
长河君 · 2026/10/8 3:21:56 · 阅读 1.2k 三数之和双指针解法全解析：从排序去重到算法面试通关
三数之和3Sum这道题几乎是我见过的刷题群里讨论热度最高的一道算法题。它不像动态规划那样劝退新手也不像图论题那样在整个算法体系里偏门它正好卡在一个“人人都能听懂解法但很少有人能一次写对”的位置。很多人能背出排序加双指针的模板但一旦被追问“为什么跳过重复元素时要用 while 而不是 if”“两个指针移动的先后顺序能不能换”“数组里有负数时剪枝条件怎么写”瞬间就露馅了。这篇文章我想把这道题从暴力解法到双指针的完整推导过程拆开讲清楚顺带分享我在面试现场和实际编码中踩过的那些坑以及它背后一套可以举一反三的思维模式。这道题适合所有正在准备算法面试的人也适合那些工作中偶尔要和数组、去重、组合条件打交道的开发人员。三数之和表面上是求三元组实际上考察的是三个基本功排序后的有序性如何被你利用、双指针收缩区间如何避免重复计算、以及如何处理“去重”这种看起来简单却暗藏细节的逻辑。把这三点吃透你收获的不只是考试分数还有一种处理有序数组问题的通用直觉。1. 三数之和到底在考什么1.1 问题定义与典型场景先明确题目本身。给你一个包含 n 个整数的数组 nums判断数组中是否存在三个元素 a、b、c使得 a b c 0你需要返回所有和为 0 且不重复的三元组。几个关键约束三元组内部顺序不重要但三元组之间不能重复也就是说 [ -1, 0, 1 ] 和 [ 0, 1, -1 ] 是同一种答案另外如果数组中存在多个相同的数值它们可以被组合进同一个三元组但同一个索引位置的元素不能重复使用。举个例子nums [-1, 0, 1, 2, -1, -4]答案集是 [ [-1, -1, 2] ] 和 [ [-1, 0, 1] ]注意这里有两个 -1它们刚好可以组成一个合法三元组而不会被视为重复使用。我一开始看到这道题时第一反应是“这有什么好考的三个循环不就完了”但如果数组长度是 3000三重循环就是 270 亿次运算任何在线评测系统都会直接超时。这才是这道题最核心的矛盾解法要快同时要保证结果不重不漏。考察的不是你会不会写循环而是你能不能理解“为什么有序数组可以用双指针把复杂度压一个量级”。很多人在 LeetCode 上提交时遇到的问题是要么结果集里出现了重复三元组要么漏掉了一些合法组合要么死循环这三个问题背后都指向同一个根源——去重逻辑没有放在正确的位置。1.2 为什么这道题在面试里这么高频三数之和在面试中出镜率极高我参加过的技术面试里至少遇到过三次类似的题目。面试官喜欢它的原因很简单它覆盖面广又能分层考察。基础差的候选人可能只能给出暴力解法中等水平的候选人能给出排序加双指针优秀的候选人能当场分析剪枝条件、内存占用和极端情况的处理。而且这道题从暴力到最优解的思维跨度很大非常适合用来判断一个人的算法直觉不需要候选人背复杂的数据结构却能通过追问不断压出深度。时至今日我仍然觉得刷三数之和比刷十道背诵型动态规划题更有价值。它背后是一整套“有序化处理”的思维方式先把数组排序让无序问题变得有结构可循再用左右指针动态逼近目标值最后通过指针跳过重复值来实现去重。这种思路在后续处理三数之和的变种时比如最接近目标值的三数之和、四数之和甚至 N 数之和都能复用。面试官一旦确认你能举一反三这个考点就完全变成了加分项而不是及格线。2. 从暴力解法到双指针的思维跃迁2.1 暴力三重循环和它的复杂度瓶颈暴力解法是每个新手接触这道题的第一站。你写三个循环枚举所有 i j k 的组合检查三元组的和是否为零再手动去重。去重怎么做大多数人会把三元组排序后放进 Set或者在收集结果时检查一下是否已经存在。这个过程代码量不小而且性能很差。三重循环的时间复杂度是 O(n^3)当 n 为 1000 时已经达到十亿级别实测下来绝对超时。但暴力解法的意义不在于性能而在于建立问题模型。你真正需要的是在 n^3 个候选中找到满足条件的那些去重只是后处理。当你盯着暴力枚举的过程看会发现大量的重复计算固定一个元素 i 后内部两重循环其实是在无序子数组中寻找两个数它们的和等于 -nums[i]。这个视角一旦建立你就意识到真正需要解决的其实是“两数之和”问题只不过这次是在排序后的数组里用双指针做。从暴力到双指针核心思想并不复杂暴力之所以慢是因为它在做无差别的枚举没有利用数组的任何结构信息。排序是一种天然的预处理手段它不改变问题的解集却把所有元素组织成了线性有序的结构。有序数组让“区间收缩”成为可能左指针向右移动会让和变大右指针向左移动会让和变小于是你可以根据当前和与目标值的比较结果只移动必要的那一侧指针。这样固定一个元素后剩下的两数查找从 O(n^2) 降到了 O(n)整体复杂度从 O(n^3) 降到了 O(n^2)。这个“排序降低维度”的思路是双指针题型的灵魂。2.2 排序加双指针最经典的主流通解整个解法的框架分三步排序、固定一个数、用双指针找两数之和。我先描述宏观流程再拆细节。第一步把数组从小到大排序。第二步从左到右遍历数组把当前元素固定为 a作为三元组中最小或第一个元素。第三步在当前位置右侧的区间里设置两个指针left 从 a 的下一位开始right 从数组尾部开始计算当前三元组的和。如果和小于 0说明整体偏小left 右移如果和大于 0说明整体偏大right 左移如果和等于 0记录这个三元组然后同时收缩两个指针继续寻找其他组合。这里有一个极其关键的认知为什么固定一个数之后剩下的两数之和必须在 a 的右侧寻找而不是在整个数组中寻找因为如果允许 left 越过 a 的位置你会产生重复的三元组比如固定了 a1在右侧找到 b2、c-3之后固定 a2又在左侧找到了 b1、c-3两个三元组其实是同一组数字只是排列顺序不同。所以从左到右固定 a每次搜索区间严格限定在其右侧天然避免了顺序导致的重复。这个设计比事后去重优雅得多也是双指针写法能够高效去重的根本原因。2.3 去重细节为什么跳过重复元素如此关键我认为三数之和最容易被忽视的地方就是去重。很多代码能跑通但结果集里有大量重复项就是因为去重位置不对。去重有两个关键位置一是外层循环固定 a 时如果当前遍历到的元素和前一个元素相同说明这个固定值已经处理过了继续走只会得到重复三元组必须跳过。这里用的是 if 跳过而不是 while 后移后继续执行因为比较的对象是 a 和前一个 a只需判断一次即可。二是内层找到和为 0 的组合时left 和 right 都要跳过重复值。一个常见的错误是只判断 nums[left] nums[left 1] 或者 nums[right] nums[right - 1] 但只移动一次那样还是可能落入重复组合。正确做法是连续跳过所有相邻重复值让指针直接落到一个新的数值上。我举个例子帮你理解。数组是 [-2, 0, 0, 2, 2]。固定 a -2 时区间内有 0 和 2。left 先指向第一个 0right 指向最后一个 2三者和为 0记录 [-2, 0, 2]。此时如果只把 left 右移一位、right 左移一位left 还是 0right 还是 2三者和仍然是 0又记录了一个重复的 [-2, 0, 2]。这就是为什么在记录完一组答案后要让指针跳过所有与当前值重复的位置然后再各收缩一位进入新的数值区间。很多自测明明通过了简单用例却在数组大量重复时失败的场景基本都栽在这里。3. 代码实现与细节打磨3.1 一份可直接上手的 Python 与 Java 实现先看 Python 实现这是我平时刷题最常用的版本def three_sum(nums): nums.sort() n len(nums) result [] for i in range(n - 2): # 剪枝数组已排序当前元素大于0则后面元素都大于0三数之和必大于0 if nums[i] 0: break # 跳过固定的重复值 if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: left 1 elif total 0: right - 1 else: result.append([nums[i], 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 return result再看 Java 版本结构完全一致只是用了 Java 的集合操作public ListListInteger threeSum(int[] nums) { ListListInteger res new ArrayList(); Arrays.sort(nums); int n nums.length; for (int i 0; i n - 2; i) { if (nums[i] 0) break; if (i 0 nums[i] nums[i - 1]) continue; int left i 1; int right n - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { left; } else if (sum 0) { right--; } else { res.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--; } } } return res; }两边代码逻辑一致你完全可以根据自己的主力语言迁移。我个人的习惯是在本地把这两个版本都跑一遍因为 Python 的处理更直观适合推导边界条件而 Java 的读者群更广适合在面试中手写时用。注意两个细节外层循环的终止条件是 i n - 2因为后面至少要给 left 和 right 各留一个位置否则会越界内层 while 条件始终要带 left right防止指针交错后还在计算和。3.2 边界条件与易错点清单我整理了一份自己在实际刷题和面试中踩过坑的易错点清单可以对照着自检。易错点具体表现正确做法忘记剪枝固定元素大于 0 仍进入内层循环数组有序nums[i] 0 时直接 break外层去重时机不对写成与后一个元素比较导致漏解应与前一个元素 nums[i - 1] 比较内层去重少了 while只跳过一次重复值仍会收集重复三元组连续跳过所有相邻重复值后再收缩指针指针收缩顺序混乱在没跳过重复值时就 left 和 right--先跳过重复后同时收缩指针固定数小于零但剪枝不生效没理解有序数组才能剪枝剪枝依赖于排序顺序必须先排序三元组顺序不一致没加“从固定位右侧搜索”的约束固定 a 后 left 从 i 1 开始数组长度为边界n 小于 3 时返回空列表先判断或让 range 自然不执行这里我想特别展开“外层去重时机”这个点。假设数组是 [-1, -1, 0, 1]外层第一次循环固定第一个 -1能找到 [-1, 0, 1]。第二次循环 fixed 到第二个 -1 时如果你写成 if i 0 and nums[i] nums[i 1] 比较的是当前元素和后一个元素当后一个元素与当前元素相同但要继续跳过时你可能会在第一个 -1 处就被误判跳过导致漏掉 [-1, 0, 1]。正确写法是 nums[i] nums[i - 1]因为你要跳过的对象是“已经作为固定位处理过的值”而不是“尚未处理的值”。这个顺序问题几乎每个新手都会踩一遍写错时还不容易察觉。3.3 复杂度分析与性能实测时间复杂度方面排序是 O(n log n)外层固定元素是 O(n)内层双指针最多移动 n 次所以双指针部分整体是 O(n^2)。最终时间复杂度为 O(n^2)。空间复杂度取决于排序算法实现如果是原地排序比如 Java 默认的 DualPivotQuicksort额外空间是 O(log n) 到 O(n)如果忽略排序栈空间可以认为辅助空间是 O(1)。对比暴力三重循环的 O(n^3)在 n 3000 时理论耗时从亿级降到了百万级差距非常明显。我在本地实测过一组随机生成的数组包含 5000 个重复度比较高的整数。暴力三重循环跑了超过 90 秒还没结束而排序加双指针版本稳定在 0.4 到 0.7 秒之间。这组数据里大量重复元素正是去重逻辑的试金石官方测试用例也经常会塞入这样的数据专门考察你没注意到的去重漏洞。如果你发现自己的代码在小数组上输出正确但提交后出现 Time Limit Exceeded多半是去重不够狠导致结果集过大内存和时间同时拉满。4. 进阶变种与扩展思考4.1 最接近的三数之和掌握了三数之和以后你应该顺手做一下它的变种题目最接近目标值的三数之和。问题描述是给定一个数组和一个目标值 target要求找出三个数使它们的和最接近 target并返回三个数的和。两题的框架高度相似唯一的区别是不用再收集所有解也不用处理三元组级去重只需要维护一个最小差值。实现时排序后固定一个数内部双指针收缩每次都计算当前和与 target 的差值绝对值如果比当前记录更小则更新答案。当当前和小于 target 时 left 右移大于 target 时 right 左移。一个重要的剪枝是如果某次当前和直接等于 target直接返回因为差值已经是 0不可能更小了。这个题目让我理解到双指针不只用于“精确寻找目标值”也适用于“逼近目标值”它本质上是一个在单调有序区间上的高效搜索策略。4.2 四数之和与 N-Sum 问题的推广学会了三数之和四数之和就是套娃。四数之和的核心思路是在外层再多套一层循环固定两个数让内部双指针在剩余区间内搜索两数之和等于剩余目标值的组合。时间复杂度从 O(n^2) 变成 O(n^3)但对有序数组的依赖不变。去重逻辑同样要出现在每一层循环里外层固定第一个数时跳过重复固定第二个数时跳过重复内层找到目标后跳过左右指针的重复。我在实际推导 N 数之和时发现一个规律N-Sum 问题本质上都是两数之和的递归化表达很多时候面试官会让你思考“如果传入的是四个数你怎么改”。答案是每多一个维度就多一层固定值的循环外层循环的层数与 N-2 成正比。这种递归思想我已经在多个算法题目中受益比如组合求和、子集生成等。吃透三数之和的双指针结构再往四数之和扩展时几乎不用背任何新东西只需要把去重规则层层复制到位。4.3 哈希表解法与空间换时间有人会问双指针是不是唯一的解法其实哈希表也能做只是通常不是最优。思路是固定两个数然后在哈希表里查询第三个数是否存在于剩余区间中。它的时间复杂度也是 O(n^2)但空间复杂度上升到 O(n)而且去重逻辑更麻烦因为哈希表是无序的你很难只用一个方向搜索来避免重复三元组。实测下来哈希表方案在多数数据集上不如双指针方案稳定特别是数组较大且重复较多时哈希表扩容带来的内存压力会和去重复杂度叠加。我理解哈希表方案的价值在于它是一个思维拓展而不是推荐的生产级方案。如果你在面试中被追问“双指针以外的解法”你可以提哈希表指出它的时间复杂度和双指针相同但空间更差还需要额外处理重复项。这个回答能展示你对时间空间权衡的完整认知比单纯说一句“双指针更好”有说服力得多。但实际写代码时我依然会选择双指针因为它的去重边界在有序数组的框架下极其清晰。5. 常见问题与排查技巧实录5.1 面试现场的高频追问面试官在面这道题时几乎不会满足于让你默写一遍代码他们通常会在你写完代码后抛出几个刁钻的问题。下面这些是我亲身遇到过的追问和自己的应对思路。第一个追问排序加双指针的解法是否稳定这个问题实际上在问去重逻辑是否会漏解。你要先解释为什么外层循环只在前一个元素相同时跳过而不是在下一个元素相同时跳过说明原因在于跳过太晚会导致重复三元组跳过太早则会让合法三元组被误杀。第二个追问如果数组中有大量负数剪枝条件是否仍然成立答案是成立。剪枝依赖于数组有序而不是取决于元素符号。当前固定位大于 0 时右侧所有数都大于等于当前值因此三者之和必然大于 0可以安全 break。注意这里说的是大于 0 而不是大于 target在三数之和中 target 固定为 0。第三个追问是很多候选人的死穴如果 nums 中包含极大整数比如 Java 中 int 溢出怎么办我在一次现场面试中就漏掉了这一点。标准双指针写法里 sum 直接使用 int 保存三个正数相加可能溢出为负数导致判断方向错误。解决方式是使用 long 保存 sum或者先将三个数中较大的值转成 long 再相加。你可以在代码里把 sum 定义为 long在比较时强转。实际工程里不一定会遇到这么大的数组值但面试官抛出这个问题时你要能立刻反应过来并给出修正方案。5.2 实际工程中的场景延伸你可能觉得三数之和这种纯算法题现实中哪会用到。其实不然。我在做数据处理需求时多次遇到过“在数据集中寻找组合满足某种约束”的场景比如在价格列表里找三件商品总价恰好落在某个目标区间内或者在推荐系统中对用户行为特征向量做组合筛选。这些需求往往不需要精确搜索全部三元组但双指针的核心思想能被迁移成“有序特征空间上的交集搜索”策略。还有一类延伸是在内存受限环境下处理流式数据。比如你有一个不断追加的时间序列数组每次新数据到达后需要查询是否存在三步移动窗口满足某种和式约束。这时你不可能每来一个数据就跑一遍完整的三数之和而是要维护有序结构并用窗口双指针增量更新。虽然工程实现复杂度远高于刷题但底层逻辑仍然是排序、单调区间、指针收缩这三板斧。所以我一直认为三数之和这类题目不该只当作考试题去背它训练的是对有序数组的敏感度这种敏感度在许多真实问题处理中都会悄悄发挥作用。最后再说一个实用的本地调试技巧当你写完三数之和的解法后先用一个含大量重复元素的小数组做测试例如 [0, 0, 0, 0, 0, 0, 0]期望答案是 [[0, 0, 0]] 且只有一条。再测试包含负数和正数交错的数组比如 [-5, -5, 1, 2, 3, 4, 10]观察是否会漏掉 [-5, 2, 3]。然后把 nums 换成反序数组确认排序逻辑正确。这些测试用例我至今保留在本地测试脚本里每次调试类似去重题目都会复用省下了大量排错时间。踩过几次坑之后我开始明白三数之和的真正难点从来不在于写出循环而在于你在思考去重与边界时是否足够严谨。