以前总觉得中等难度的算法题“中等”两个字意味着思路要绕好几个弯直到我做到三数之和这道题才发现真正难的往往不是复杂思路而是各种边界细节和去重逻辑交织在一起。作为刷题打卡的第六天这道题对我来说像是一道分水岭理解了它“双指针排序”这个套路就能打通一大片题目没吃透它后面遇到四数之和、最接近的三数之和照样会卡壳。题目本身其实不难描述给你一个整数数组 nums判断是否存在三个元素 a、b、c使得 a b c 0。要求返回所有满足条件且不重复的三元组。注意答案里不能包含重复的三元组这里的“不重复”是整道题最容易被忽视、也最值得展开讲的坑。这个题适合所有准备算法面试的人也适合刚学完数组和指针、想进阶到双指针思想的初学者。它能帮你建立一套写边界条件的肌肉记忆告诉你什么情况下排序是值得的、什么时候哈希表反而不是最优解、循环里到底该怎么跳过重复元素才不会又漏又重。1. 题目到底在考什么表面求和内里考去重很多人拿到这道题的第一反应是“不就是找个三数之和等于零嘛三层循环暴力扫完事”。我在没看题解前也是这么想的。但真动手写就会发现问题三层循环的代码只要十行跑起来却慢得离谱而你要是为了快一点加入各种剪枝又很容易陷入“这个三元组算了、那个三元组没算”的混乱。先明确一下题目的输入输出边界。LeetCode 给的函数签名是threeSum(nums: List[int]) - List[List[int]]。一组典型的输入是[-1, 0, 1, 2, -1, -4]期望的输出是[[-1, -1, 2], [-1, 0, 1]]。注意这里有两个以 -1 开头的不同三元组为什么它们不叫重复因为三元组的元素值不同一个带 2一个带 0 和 1只要下标组合不同、数值组合不同两个三元组就算不同。但如果输入是[0, 0, 0, 0]输出只能是[[0, 0, 0]]不能输出 4 个同样的[0, 0, 0]。这个细节直接决定了你要不要在循环里做特殊去重处理。我一开始踩的坑就是没想清楚“去重”到底以什么为标准。网上有些教程说“先排序再去重”但排序只是工具它让重复的元素挨在一起方便跳过真正判断重复靠的是“同一位置不能出现相同数值”。也就是说固定的第一个数 nums[i] 如果和前一个数 nums[i-1] 相同那这一轮枚举一定是上一轮的重影必须跳过。双指针移动过程中左侧指针遇到相同的数也要一掠而过。这些细节不是锦上添花的优化而是答案正确性的保证。还有一点值得说这道题为什么是“中等”而不是“简单”因为暴力法的时间复杂度是 O(n^3)在 n 能达到 3000 的量级下完全不可行。你不仅要知道怎么优化到 O(n^2)还要在 O(n^2) 的基础上保证回答不重不漏。这考察的其实是计算机里一个很核心的思想通过预处理排序把无序问题变成有序问题再用单调性把复杂度降一个维度。用生活里的事打个比方你去水果店买三种水果凑正好一百块如果价格单是乱序的你只能一个一个问老板“这个配那个多少钱”如果价格从便宜到贵排成一行你从最便宜的往贵的方向走从最贵的往便宜的方向走两头慢慢往中间试这就快多了。双指针本质上就是这种“两头逼近”的思路。2. 从暴力到双指针为什么非得排序凭什么能省一层循环2.1 暴力循环的计算量到底有多可怕我们先不聊优化先把暴力解老老实实写出来def threeSum_bruteforce(nums): n len(nums) res [] seen set() for i in range(n): for j in range(i 1, n): for k in range(j 1, n): if nums[i] nums[j] nums[k] 0: triplet tuple(sorted([nums[i], nums[j], nums[k]])) if triplet not in seen: seen.add(triplet) res.append(list(triplet)) return res这个实现能跑通小数据但 n 到 1000 时已经是 10 亿次运算量n 到 3000 时是 270 亿次。再加上每次还要排序三元组、查集合耗时直接指数起飞。我在本地试过n2000 时这个函数已经要跑十几秒完全不符合在线判题的时间预期。更隐蔽的问题在于暴力法为了去重不得不用集合保存三元组而集合里的元素又必须可哈希所以要对[a, b, c]先排序再转 tuple。这一步额外引入了 O(n^3 log 3) 的排序开销代码也不优雅。说白了暴力法的时间复杂度不只是 O(n^3)还带了一个常数不小的“去重尾巴”。2.2 排序之后问题一下子“线性”了双指针解法的核心不是三个指针一起动而是“固定一个动两个”。流程是这样对 nums 排序让元素从小到大排列。从 0 到 n-3 枚举第一个数 nums[i]。在 [i1, n-1] 这个区间内给左指针 left 和右指针 right 分别指向区间两端。计算current_sum nums[i] nums[left] nums[right]若 current_sum 0记录结果然后 left 右移、right 左移并跳过重复值。若 current_sum 0说明整体太小需要更大的数left 右移。若 current_sum 0说明整体太大需要更小的数right 左移。枚举下一个 i重复以上过程。关键点在于排序以后数组具有单调性。左指针往右移和值只会增大或不变右指针往左移和值只会减小或不变。这样每轮移动指针都是在往目标方向靠近绝不会走回头路。双指针整体扫描一遍区间是 O(n)再加上外层枚举是 O(n) 次所以双指针阶段是 O(n^2)排序阶段是 O(n log n)总复杂度就是 O(n^2)。这里顺带解释一个初学者常见疑惑为什么不是先枚举两个数、再用二分找第三个数那样是 O(n^2 log n)虽然也能过但不如双指针直接 O(n^2) 清爽。双指针的妙处在于它把“在剩余区间找两数之和等于目标值”这件需要 O(n) 的事和区间边界的变化绑定在一起省掉了二分查找的额外 log 因子。另外注意一点因为题目要求三数之和等于 0我们固定第一个数之后剩余要找的两数之和就是-nums[i]。那么问题就退化成了“两数之和等于某个 target”这正是双指针最擅长的形态。这个转换很关键它把三数之和拆成了“一个固定数 一个两数之和子问题”而在有序数组里两数之和用双指针求解既不需要哈希表也不需要额外空间。3. 完整代码实现与逐段拆解这 25 行代码里藏了 5 个细节先给出最终版本代码我用 Python 写因为刷题时 Python 写起来最快逻辑也最清晰def threeSum(nums): n len(nums) if not nums or n 3: return [] nums.sort() res [] for i in range(n - 2): # 剪枝第一个数都大于 0后面不可能凑出负数 if nums[i] 0: break # 对第一个数去重 if i 0 and nums[i] nums[i - 1]: continue left i 1 right n - 1 target -nums[i] while left right: current_sum nums[left] nums[right] if current_sum target: res.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 elif current_sum target: left 1 else: right - 1 return res3.1 为什么剪枝条件写nums[i] 0而不是nums[i] 0因为数组是递增排序的一旦固定的 nums[i] 大于 0那后面的 nums[left] 和 nums[right] 也都大于 0三个正数永远加不出 0。此时直接 break 跳出整个循环节省后续所有无效枚举。但是 0就会出问题——如果 nums[i] 等于 0后面可能还有[0, 0, 0]这种合法三元组一 break 就漏解了。这个细节我在第一次写的时候踩过想“优化”一下写成 0结果 5 个 test case 里挂了两个。3.2 第一个数去重为什么要比较nums[i]和nums[i-1]而不是nums[i1]区别非常大。如果写if nums[i] nums[i 1]: continue你跳过的是“以当前 i 作为第一个数”的所有组合但问题在于nums[i]和nums[i1]相同不代表以 nums[i1] 开头的组合是重复的——实际上以 nums[i] 开头的组合才是第一次出现的那组。这个写法会把第一次出现的组合也跳过导致漏解。正确做法是“如果一个数跟前一个数相同那它一定是上一轮的重复跳过”。所以在进入循环体之前检查nums[i] nums[i-1]。这个 i 从 0 开始要额外加上i 0防止数组越界访问nums[-1]。写题多了你会发现这种“索引边界 去重方向”的错误是算法题里最常见的翻车点。3.3 和等于 0 之后内层两个 while 去重的顺序很多新手会问既然找到了nums[left] nums[right] target直接 left、right-- 不行吗梳理一下实际会发生什么。如果区间里有连续重复元素比如排完序后有一段[-1, -1, 0, 1, 1]left 指向第一个 -1right 指向第二个 1 时找到了结果。此时如果不做内层去重left 移到 0right 移到第一个 1计算0 1 target(-(-1))不成立继续移动等到 left 指向第二个 -1、right 指向第一个 1 时又会找到和刚才一模一样的[-1, -1, 1]不对这里数值变了得看具体例子。更直接的例子是nums [-1, -1, -1, 0, 0, 1, 1, 1]。当 i0 固定第一个 -1target1left 指向下标 1 的 -1right 指向下标 7 的 1。和为 0-1 1 0不是 target 1。再移动left 走到下标 2 的 -1right 走到下标 3 的 0加起来 -1 还是小于 1left 继续走……整个过程很难遇到重复输出。但换个例子[-2, -1, -1, 0, 1, 2, 2]i0 固定 -2target2left1-1right62和为 1 不等于 2right 需要减到 2中间可能多次组合。当 left1、right5 时和是 1left1、right4 时和是 0left2、right6 时和是 1……这轮走完不会发现等于 2 的组合。说这些是想告诉大家内层去重的必要性不能靠“理论上可能重复”来解释它其实针对的是“找到一次相等后还把指针只移动一小步导致下一轮又发现同一个组合”的情况。比如[-1, -1, 2, 2]配合 target-1 的场景i 固定某个数left 指 -1、right 指 2 时 sum 正好相等。如果只做left 1; right - 1left 移到第二个 -1right 移到第一个 2又满足相等于是输出两遍[固定数, -1, 2]。这两份三元组下标不同、元素值却完全相同属于题目明确禁止的重复答案。有了内层两个 while就可以把 left 和 right 一口气推到连续相同元素的边界之外从根上杜绝这种重影。3.4 为什么每次只移动一个指针就能保证不遗漏这背后是“有序数组 双指针收敛”的正确性证明。固定 nums[i] 之后区间 [i1, n-1] 里任意一对 (left, right) 的候选组合都有且仅有一次被访问的机会。当current_sum target时说明nums[left] nums[right]太小而 right 已经是区间里最大的几个数之一想让和变大只有 left 往右移一条路。反过来current_sum target时left 已经是最小的数想让和变小只有 right 往左移。所以每次移动都是在“排除掉不可能产生答案的一整条线”而不是随意排查最终一定扫过所有可能组合。这个证明思路面试时如果被追问答出来就是加分项。3.5 时间与空间复杂度到底怎么算排序的时间复杂度是 O(n log n)枚举 i 是 O(n)内层双指针是 O(n)所以总时间复杂度是 O(n log n n^2) O(n^2)。空间上Python 的 sort 排序用到临时空间一般算 O(log n)如果不计输出数组 res 占用的空间额外空间就是 O(1)。这也是这个解法比“哈希表 去重集合”更优秀的地方——很多哈希表写法虽然也是 O(n^2)但额外空间复杂度是 O(n)。4. 常见错误与排查技巧实录我花了整整一天才把所有坑填平4.1 问题一没排序就启动双指针结果答案全错双指针为什么能成立前提就是区间有序。我第一次偷懒想省掉排序这一步结果 left 和 right 移动完全没有章法current_sum target时 left 右移但这个 left 右边的数可能比当前 left 还小移动过去之后和反而变小了整个搜索方向就乱了。最后输出要么漏解、要么死循环。解决办法很简单先排序再双指针。排序不是可选项是必选项。而且因为题目是要求返回三元组的具体值、不要求保留下标所以排序不会破坏任何需要的信息。4.2 问题二去重位置放错导致答案少了还有重复我去重逻辑最早写在 while 循环的最前面也就是每次进入循环先判断 left 和 left1 是否相同、right 和 right-1 是否相同相同就移动跳过。结果悲剧了[-1, 0, 1, 1]这种输入当右指针指向第二个 1 时发现和前一个重复直接跳过了导致漏掉了[-1, 0, 1]这个合法答案。正确的位置是只在找到current_sum target之后才去做内层去重。在一轮查找过程中中间状态的重复元素不能轻易跳过因为它们可能在后续移动中形成不同的组合。这点非常反直觉建议每写一遍都提醒自己一次。4.3 问题三找到答案后忘了移动指针陷入死循环如果current_sum target时只是记录结果不执行 left 和 right--下一轮 left right 仍然成立sum 还是 target又会记录一模一样的结果……然后死循环。不少新手包括我犯这个错是因为写 if-elif 时漏了“相等分支也要动指针”这个操作。记住只要 left 和 right 都动一步循环才能朝终止前进。4.4 问题四for 循环边界写错落下了最后两三个元素for i in range(n - 2)而不是range(n)因为 i 之后必须至少留两个位置给 left 和 right。同理内层双指针的条件是while left right不是while left right因为同一个元素不能复用。这些边界看着简单但在大段调试里很容易被忽略尤其是当输入数组很长、你盯着输出列表找重复项找到眼花时越基础的地方越容易出问题。4.5 问题五直接修改原数组导致后续测试用例出错刷题平台是多个测试用例共享同一个进程的如果你在函数里直接对传入的 nums 调用 sort()它会原地修改原列表。虽然 Python 的 List[int] 参数是引用传递函数结束后外部变量也会变有可能影响下一个 test case 的输入。好在 LeetCode 内部每个用例都会新构造输入所以影响不大。但如果你在自己的测试脚本里批量跑建议用sorted(nums)生成新列表避免引用污染。# 安全写法不修改外部引用 sorted_nums sorted(nums)4.6 常用调试手法自己跑这些边界用例我后来养成一个习惯写完代码先不过脑子看题解而是手动跑一组针对性测试用例输入期望输出验证目的[][]空数组边界[0][]不足三个元素[0,0,0][[0,0,0]]全零最简单用例[0,0,0,0][[0,0,0]]最严格去重[-1,0,1,2,-1,-4][[-1,-1,2],[-1,0,1]]官方标准用例[-2,0,1,1,2][[-2,0,2],[-2,1,1]]验证右指针回退时能发现右端重复组合[3,0,-2,-1,1,2][[-2,-1,3],[-2,0,2],[-1,0,1]]验证多个不同三元组并存把这些用例全跑通基本可以说明代码没有大方向问题。剩下的就是随机数据对拍拿暴力求解结果和双指针结果对比数据规模 n ≤ 12 时二者应当完全一致。5. 从三数之和出发一类双指针题型的底层套路5.1 这类题的通法总结做完三数之和再回头看会发现一个高度可复制的套路排序原数组。外层枚举第一个数内层用双指针扫描剩余区间。固定第一个数时遇重复值跳过。双指针内找到目标后左右指针同时移动并跳过重复值。根据当前和与目标大小关系决定移动左指针还是右指针。这个套路能直接迁移到很多题两数之和 II输入有序数组、三数之和的变形、四数之和、最接近的三数之和、三数之和小于目标值的数量统计等等。刷题不是刷一道忘一道把套路抽出来才能用一个思想解决一批题。5.2 面试时怎么把这题讲得比别人好面试官让手撕三数之和时很多候选人会直接开始写代码其实最优流程是先和面试官确认输入数组是否可能极长数值范围是否有 int 溢出风险返回的三元组顺序是否有要求这些问题能展示你的工程思维。再快速讲一遍思路先排序再固定第一个数然后用双指针找两数之和。解释为什么排序能让双指针成立。然后写代码重点标注去重逻辑的位置并说明为什么在找到结果后才跳过重复元素。最后手动走一遍[-1,0,1,2,-1,-4]展示输出[[-1,-1,2],[-1,0,1]]的生成过程顺带验证去重。这套流程下来比闷头写代码的候选人看起来专业得多。面试官要是追问“如果数组里有大量重复值怎么办”你就把那两个 while 去重的细节讲清楚要是追问“能不能用哈希表实现”你可以说明能用但空间复杂度是 O(n)而且去重更麻烦双指针综合更优。6. 从刷题到实战这道中等题教会我的三件事6.1 代码量不等于难度边界条件才是三数之和的解法代码只有二十多行比很多简单题还短。但它能成为经典中等题恰恰是因为那些藏在角落里的边界条件。写算法题最忌讳一上来就埋头写主逻辑先把边界条件写清楚后面才有得谈。6.2 排序这个预处理动作的价值被严重低估很多题看到“无序数组”就觉得只能哈希表或暴力。但别忘了排序只花 O(n log n)之后解决的问题就可能从完全随机变成有序结构后者的解题手段丰富得多。遇到无序数组 需要查组合的题目先把“能否排序”加入考虑清单说不定一条新路就打开了。6.3 去重逻辑是工程里最常见的隐形需求工作里写接口、写数据处理脚本“重复”永远是绕不开的问题。三数之和里的这种去重思想其实和业务开发里“同一身份证注册多个账号要合并”“日志里同一条错误要聚合去重”是一回事。刷题不仅能应付面试也是在练这种处理真实数据时的严谨性。这道题刷完以后我回头再看自己项目里那段重复数据清理逻辑突然觉得当初写得不够好又重构了一遍——这算是刷题的意外收获。最后分享一个我个人的小习惯刷到这种经典题不要只看题解就觉得自己会了最好隔一天、隔一周各默写一遍。等到你闭着眼都能把去重的三个位置默写出来、并且知道为什么它们要分别放在那里三数之和这道题才算真正过了关。