三数之和双指针解法：排序去重与复杂度优化-北京尧图网络

1. 先看清题目在考什么1.1 题目要求与典型输入输出三数之和3Sum是 LeetCode Hot 100 里一道非常经典的中等难度题题目本身很短给定一个整数数组nums要求返回所有和为 0 且不重复的三元组三元组内部和三元组之间都不能重复。举个典型例子输入nums [-1, 0, 1, 2, -1, -4] 输出[ [-1, -1, 2], [-1, 0, 1] ]注意这里有个很容易忽略的细节数组里有两个-1但最终三元组[-1, 0, 1]只能出现一次。也就是说去重不是简单地去重数组元素而是要去重最终的结果三元组。这个要求直接决定了整个解法的设计方向。1.2 这道题的真实考点刷题经验丰富的人应该能感觉到这道题考察的不是你会不会三重循环而是三个层面的能力能不能把问题降维。三数之和的本质是在固定一个数之后把问题退化成两数之和。懂不懂双指针的适用前提。双指针不是万能的它要求数组有序。为什么排序是前置条件很多新手没想明白。能不能干净地处理去重。这是这道题区分度最高的地方面试官基本都会追着问。在 Hot 100 里这道题的价值在于它是一大类题目的母题。后面我会讲到四数之和、最接近的三数之和全都是在这个框架上做小改动。所以这道题值得花时间彻底吃透而不是背个答案就完事。2. 为什么暴力三重循环注定过不了2.1 暴力法有多慢最直观的思路是三重循环枚举所有组合判断每组和是否为 0。代码很简单三分钟就能写出来但问题在于复杂度O(n³)。当n是 3000 的时候运算量大约是 270 亿次这显然是不可接受的。就算n只有 5001250 万次操作在 LeetCode 上也会卡在超时边缘。所以暴力法在思路上没错但在工程上不可行这也是 LeetCode 这类题目存在的意义——逼你去想更优解。2.2 去重才是真正的难点很多人第一次写暴力法会发现一个更头疼的问题即使三重循环能跑完结果里会有一堆重复三元组。比如[-1, 0, 1]和[0, -1, 1]从集合角度看是同一个三元组但三重循环会把它们当成两组不同的结果分别输出。想要去重最简单的方法是先把每个三元组排序再放进Set里去重。但这样做的成本很高排序三元组需要额外时间Set存储需要额外空间而且代码写起来很啰嗦。暴力法的这两个痛点——慢和重复——恰恰是正解要解决的核心问题用排序把重复元素聚拢用双指针把 O(n³) 降到 O(n²)同时天然规避重复结果。3. 排序双指针三数问题的标准解法3.1 核心思路把三元组拆成固定一个两数之和想清楚一个问题如果数组已经有序我们固定第一个数nums[i]那么剩下两个数的目标值就变成了target -nums[i]。此时问题退化成在i后面的有序子数组中找到两个数相加等于target。在有序数组里找两数之和这个问题就是经典的双指针场景。用两个指针分别指向子数组的头和尾根据当前和与目标值的大小关系决定移动左指针还是右指针一次遍历就能找到所有组合单次查找的复杂度是O(n)。外层固定第一个数需要遍历一遍所以整体复杂度就是O(n²)。相比暴力法这是一个质的飞跃。3.2 双指针怎么移动双指针的移动逻辑是这道题最顺滑的部分理解它比记住代码重要得多。假设left指向i1right指向数组末尾sum nums[left] nums[right]如果sum target说明找到一组有效解记录结果然后left、right--同时向中间靠拢。如果sum target说明整体偏小需要把left往右移让和变大。如果sum target说明整体偏大需要把right往左移让和变小。这里有个值得深挖的问题为什么可以放心地移动指针因为数组有序left右边的数一定不小于nums[left]right左边的数一定不大于nums[right]。所以sum target时右移left是唯一能让和变大的方向反之亦然。这种单调性是双指针正确性的根基。3.3 去重的三个关键位置这是整道题最容易翻车的地方我把它拆成三个位置分别讲清楚。第一个位置是外层固定数nums[i]的去重。如果nums[i]和前一个数nums[i-1]相等那么本轮能产生的所有三元组在前一轮已经全部产生过了直接continue跳过本轮。注意这里比较的是nums[i]和nums[i-1]而不是nums[i1]。如果拿后者去比较会漏掉[-1, -1, 2]这种第一个数连续重复但整体有效的组合。第二个位置是找到一组解之后对nums[left]去重。找到一组解后如果紧挨着的下一个数和当前left指向的数相同那下一组解必然重复所以要用while循环把left一路向右挪到最后一个重复数。第三个位置和第二个对称是对nums[right]去重。处理完重复后再各自移动一步进入新的区间继续找。这三个位置缺一不可。漏掉第一个结果会有重复的首元素漏掉后两个结果会有一大批重复三元组。我见过很多人代码逻辑全对就因为去重位置写错提交直接红一大片。4. 代码落地Python 与 Java 实现与逐行拆解4.1 Python 实现def three_sum(nums): nums.sort() n len(nums) result [] for i in range(n - 2): # 剪枝最小的数已经大于 0后面不可能三数和为 0 if nums[i] 0: break # 外层去重跳过重复的第一个数 if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 target -nums[i] while left right: current_sum nums[left] nums[right] if current_sum target: 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 elif current_sum target: left 1 else: right - 1 return result这段代码里我建议你重点关注两处。第一处是nums[i] 0的剪枝因为数组已经从小到大排好序了如果当前固定的数都大于 0那后面的数只会更大三数之和无论如何不可能等于 0直接结束整个循环。这个剪枝看似微小但在极端数据比如全为正数的数组下能省掉大量无意义的遍历。第二处是去重的while循环必须放在找到一组解之后执行而不是放在进入while循环的开头。这个顺序问题很关键我会在后面单独展开。4.2 Java 实现public ListListInteger threeSum(int[] nums) { Arrays.sort(nums); ListListInteger result new ArrayList(); 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, right n - 1; int target -nums[i]; while (left right) { int sum nums[left] nums[right]; if (sum target) { result.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--; } else if (sum target) { left; } else { right--; } } } return result; }和 Python 版本逻辑完全一致区别只在语言语法。如果你面试用 Java需要注意Arrays.sort(nums)是原地排序会直接修改原数组这在面试时需要和面试官确认是否允许不过 LeetCode 默认是允许的。4.3 几个容易写错的细节我自己在刷这道题的时候反复犯错的基本集中在几个点上写出来给各位提个醒。外层循环的上界。for i in range(n - 2)不是range(n)因为固定第一个数之后后面至少要留两个位置给left和right。如果写成range(n)当i接近数组末尾时left和right会越界。left和right的初始值。left必须从i1开始不能从 0 开始。如果从 0 开始就会出现同一个元素被重复使用的情况违反题目中i ! j的要求。内层去重的指针移动。找到一组解后两个while循环负责跳过重复值然后必须额外执行一次left和right--。很多人只写while循环忘了最后这一步结果指针卡在最后一个重复元素上下一个循环又进入相同状态直接死循环。这几个细节每个我都真实踩过而且每次都是提交之后报错了才回头排查所以干脆在这里一次性写清楚。5. 实战踩坑记录边界、死循环与剪枝5.1 死循环是怎么产生的提到死循环我拿一次实际调试经历来说。当时我写完代码自以为逻辑没问题提交之后发现超时。回头一查问题出在while循环的去重逻辑上。我原本的写法是找到一组解后先left、right--然后再用while跳过重复。这种写法在跳过重复时如果发现左右指针中间已经没有别的元素了循环就结束了但如果还有元素就可能在跳过过程中错过一次判断导致某一轮left和right的组合重复计算。更典型的死循环场景是找到一组解后只做了while跳过重复但跳过之后没有继续移动指针下一次循环进来发现nums[left]和nums[right]的和还是原来的值又重复记录一次同样的三元组进入死循环。正确的顺序是先跳过重复再做一次指针移动。这两个动作缺一不可顺序也不能换。5.2 剪枝优化什么时候可以提前退出除了前面提到的nums[i] 0剪枝还有一个隐藏优化的点nums[i] nums[i1] nums[i2] 0时也可以提前结束因为这是当前i位置能组成的最小三数和它都已经大于 0 了后面的组合只会更大。同理如果nums[i] nums[n-2] nums[n-1] 0说明当前i能组成的最大三数和都小于 0这时不需要直接跳出整个循环但可以continue到下一位i因为换个更大的nums[i]还有可能让和变大。这两个剪枝在实际面试中属于加分项能体现你对边界条件的敏感度。不过在 LeetCode 的测试数据下不做这两个剪枝也能通过因为它们主要影响常数不影响复杂度量级。5.3 常见问题速查表症状原因解决方法结果包含重复三元组外层或内层去重位置写错按 3.3 节的三个位置逐一检查提交超时用了暴力三重循环改为排序双指针降到 O(n²)程序卡死找到一组解后指针没移动先跳过重复再left/right--数组越界外层循环上界写成n改成n - 2给双指针留位置结果缺少部分组合外层去重错误地用了nums[i1]做比较改为和nums[i-1]比较其中结果缺少部分组合这个坑我周围不少朋友都踩过。和nums[i1]比较会导致什么后果拿[-1, -1, 0, 1]举例当i0时nums[0] -1此时nums[i]不等于nums[i1]-1 ! -1为假所以不会跳过能正常找到[-1, 0, 1]但i1时nums[1] -1和nums[2] 0比较虽然当前首元素和前一轮重复了但没被跳过于是又找了一遍最终结果是重复。这看起来只是重复问题但在某些特殊用例下会因为重复占用结果集导致原有的组合被覆盖或漏掉表现成缺少部分组合。6. 同类题串讲两数之和、四数之和与最接近的三数之和6.1 两数之和从哈希表到双指针两数之和是三数之和的前置问题。经典的解法是用哈希表遍历数组检查target - 当前数是否已经在哈希表里复杂度O(n)。但到了三数之和为什么不能用哈希表原因在于三数之和要求返回所有不重复的三元组哈希表在处理去重时非常被动。而双指针配合排序天然把重复元素聚拢在一起去重变得非常自然。如果有兴趣可以思考一个变体如果数组是有序的两数之和也可以用双指针做复杂度同样是O(n)。这正是三数之和内层循环所复用的思想。6.2 四数之和双层循环双指针四数之和4Sum是三数之和的直接扩展外层固定第一个数内层再固定第二个数剩下两个数用双指针找。整体复杂度O(n³)。在实现上四数之和需要做两层去重外层两个数的去重逻辑和三数之和的外层去重一模一样内层双指针的去重也完全复用。所以如果你把三数之和的代码彻底吃透了四数之和基本就是复制粘贴改一改的问题。另外四数之和有一个不同点目标值不是 0而是外部传入的target所以不能使用nums[i] 0那种剪枝需要根据目标值的正负做更精细的判断。6.3 最接近的三数之和最接近的三数之和3Sum Closest是三数之和的另一个变体给定一个目标值找到三元组和与目标值的差最小。解法框架完全一模一样排序固定一个数双指针。区别在于不需要严格等于 0而是维护一个最小差值。每次计算当前三数和与目标值的距离如果距离更小就更新答案。如果当前和恰好等于目标值直接返回这是最优解。这道题比三数之和更好写因为不需要处理去重双指针移动逻辑也简单只要比较abs(sum - target)即可。我建议刷题时把这三道题放在一起做对比它们的异同比单独刷十道题效率高得多。刷完这些变体之后你会发现三数之和真正教给你的不是那几行代码而是一种如何把复杂问题拆成已知问题的思维方式。固定一个维度剩下的用双指针解决这个套路在后续很多算法题里都会反复出现。我自己刷这道题花了整整一个周末前几次提交都是去重错误每次调试都忍不住想直接看答案。但回过头看恰恰是那些报错的瞬间让我真正理解了双指针和去重的本质。所以如果你也被这道题卡住了别急着翻题解先自己把代码写出来哪怕一遍遍地调试这个过程本身比答案值钱得多。

三数之和双指针解法：排序去重与复杂度优化

相关推荐

84674

生物数学：概念、历史、内容、挑战与展望！

62453

更多资讯

AI视频生成异步任务管理：查询API与轮询策略实战

论文写作前的资料整理怎么做：按素材分类与提纲对应的四条判据

OM1到OM5多模光纤全解读：选型、距离与现场施工避坑指南

Word文档防修改完整指南：从只读到密码加密的实用方案

蛋白表达标签怎么选？His、GST、MBP、SUMO与Tag-free无标签策略技术对比

数据可视化高颜值秘籍：22个布局与配色高阶技巧详解

今日更新

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？