两数之和、三数之和这两道题在国内外的算法刷题榜单上常年霸榜。尤其是两数之和基本上所有人刷力扣的第一题就是它。坦白说我一开始刷这两道题的时候也是背题解过来的——两数之和用哈希表三数之和排序加双指针背得滚瓜烂熟但换一道变体题就当场懵住。后来刷得多了才想明白一个事这两道题属于“套路型题目”套路背后是两种极其重要的基础算法思维——查表法与双指针收缩。把它们彻底吃透性价比极高你后面刷四数之和、最接近的三数之和、和为定值的子数组这类题都会轻松很多。这篇笔记我按自己的复盘方式重新整理了一遍从暴力思路推导到最优解每一步都说清楚“为什么要这么写”Python3代码直接放在对应的解析后面。适合刚刷完数组基础、准备系统性学习算法题的朋友也适合准备面试前快速过一遍经典模板的求职党。1. 两数之和从暴力枚举到哈希表的思维跃迁1.1 先看清题目到底在问什么题目描述很简单给定一个整数数组nums和一个整数目标值target请在数组中找出和为目标值的那两个整数并返回它们的数组下标。这里有两个容易忽略的细节一是返回的是下标不是元素本身二是每种输入只会对应一个答案但数组里同一个元素不能重复使用。第一点决定了我们不能直接排序后用双指针因为排序会打乱下标关系第二点则天然迎合了“边查边存”的哈希表思路。我第一次做这道题时第一反应就是双层循环固定第一个数往后遍历找有没有target - nums[i]。这个思路确实能过测试但效率太差了。按最坏情况算一个长度为 n 的数组需要比较约n*(n-1)/2次当 n 到 10000 时直接就是近五千万次比较本地跑还能忍放到判题机上基本就是超时边缘。暴力解法不是没有价值它是我们推导更优解法的起点。把暴力解的核心逻辑抽象出来——找到“目标数”和“当前数”的配对关系你会发现真正的性能瓶颈在于每次查找target - nums[i]都是在剩下的数组里线性扫描这个“查找”操作是 O(n) 的。如果能把这个 O(n) 的查找变成 O(1)那总复杂度就能从 O(n²) 降到 O(n)。1.2 哈希表为什么是更优解把查找变成 O(1)最直接的工具就是哈希表也就是 Python3 里的字典dict。字典的底层是哈希表结构平均增删查操作都是 O(1) 时间复杂度。用字典解题的核心思路是“边遍历、边记录、边查找”我们每遍历到一个新元素nums[i]就去字典里查有没有target - nums[i]。如果存在说明之前某个下标对应的值正好和当前值互补那就直接得出答案如果不存在就把当前元素的值和下标存进字典留给后面匹配。这种做法的精妙之处在于它天然保证了“同一个元素不会重复使用”因为我们是先查字典再往字典里存入当前元素。也就是说当遍历到某个元素时字典里存的只有当前元素之前出现过的元素当前元素还没有被放进去自然不存在自我匹配的问题。我们拿一个简单例子走一遍流程。假设nums [2, 7, 11, 15]target 9初始化字典seen {}遍历到2查9-27不在字典中存入{2: 0}遍历到7查9-72正好在字典中键2对应的值是索引0返回[0, 1]整个过程只遍历了一次数组时间复杂度 O(n)额外使用了一个字典存储数据空间复杂度也是 O(n)。1.3 两数之和的Python3标准写法def two_sum(nums, target): seen {} for i, num in enumerate(nums): complement target - num if complement in seen: return [seen[complement], i] seen[num] i return []这套代码是刷题圈流传最广的模板看起来极简但有几个细节值得反复咀嚼。第一个细节enumerate的用法。它同时拿到下标和元素值比手写for i in range(len(nums))更简洁也更符合 Python3 的惯用法。第二个细节判断用complement in seen而不是complement in seen.keys()后者在 Python3 里会多一层包装调用虽然差距很小但刷题时养成绩优习惯没坏处。第三个细节先查再存。顺序一旦调反遇到重复元素时可能返回错误结果。注意如果题目改成“返回元素值本身”那用单纯的哈希集合set就够了不需要存下标。但本题是返回下标所以必须用字典来存“值到索引”的映射关系。2. 三数之和排序双指针把 O(n³) 压到 O(n²)2.1 为什么不能直接套两数之和的哈希法三数之和的要求是给定数组nums判断数组中是否存在三个元素 a、b、c使得a b c 0返回所有满足条件且不重复的三元组。看到“三数之和是两数之和的升级版”很多人的第一反应是在三数之和里套一层循环固定第一个数剩下两个数用两数之和的哈希法来找不就行了吗这个方法理论上可行但有一个极其致命的痛点——去重非常麻烦。两数之和不用去重是因为题目保证了答案唯一。但三数之和要返回所有不重复的三元组用哈希法实现去重要么先把三元组排序再放进 set要么用复杂的组合条件去判断是否出现过。前者需要大量的哈希计算和存储后者容易把判断条件写得漏洞百出。而且哈希法在处理“返回所有结果”的遍历路径时不够自然代码写出来又长又绕。排序加双指针就用一种非常优雅的方式消解了这个问题先把数组排好序让相同的元素紧挨在一起这样在移动指针时只要跳过相邻的相同元素就能天然避免重复三元组无需额外的 set。这是三数之和这道题背后真正值得学习的思维拐点——用有序性换取去重的便捷性。2.2 排序双指针的推导过程排序双指针的完整推导我习惯分成三个层次去理解。第一个层次是“固定一个数转化为两数之和”。我们在外层循环固定一个数nums[i]问题就变成了在剩下的数组区间[i1, n-1]中找到两个数和等于-nums[i]。这一步把三数问题降维成了两数问题。第二个层次是“双指针在一段有序区间里找两数之和”。因为数组已经排序区间内的元素是从小到大排列的。我们在区间最左端放一个指针left i1最右端放right n-1。计算sum nums[i] nums[left] nums[right]然后根据 sum 与 0 的关系调整指针如果sum 0找到了一个合法三元组记录下来同时移动左右指针继续寻找下一种组合如果sum 0说明当前的三个数之和偏小需要把指针往更大的方向移动也就是left 1如果sum 0说明偏大把right - 1这里需要理解的关键是为什么移动指针就能保证不漏解因为数组有序left往右移动意味着和增大right往左移动意味着和减小这种单调性保证了我们枚举的所有和有明确的走向不需要盲目的暴力搜索。每做一次判断就排除掉一整行或一整列的无效组合这是双指针高效的本质。第三个层次是“去重逻辑”。去重有两个位置外层固定的数要去重内层找到答案后的指针移动也要去重。外层去重很好理解固定的第一个数相同后面找出的所有组合一定相同简称“同一位置重复无意义”。内层去重则是当nums[left]和nums[left1]相同时左指针直接跳到最后一个相同的值右指针同理。这个去重的写法是整道题最容易写错的地方后面我会专门展开说。2.3 三数之和的Python3标准写法def three_sum(nums): nums.sort() n len(nums) result [] for i in range(n - 2): # 外层去重 if i 0 and nums[i] nums[i - 1]: continue # 剪枝最小的三个数都大于0后面不可能有解 if nums[i] nums[i 1] nums[i 2] 0: break # 剪枝当前数加上最大的两个数都小于0当前数太小换下一个 if nums[i] nums[n - 1] nums[n - 2] 0: continue left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: 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 total 0: left 1 else: right - 1 return result这套代码我反复手写了很多遍越写越觉得里面每个判断都有讲究。先看外层去重的写法if i 0 and nums[i] nums[i - 1]。这里必须是nums[i] nums[i-1]不能是nums[i] nums[i1]。原因很微妙如果用nums[i] nums[i1]会直接把当前轮次跳过导致漏掉[-1, -1, 2]这种情况因为第一个 -1 和第二个 -1 相邻用后向比较会把第一个 -1 直接判为重复而事实上第一个 -1 是有用的。再看剪枝的两个判断这是性能优化技巧不是必写代码但写上之后能避免大量无效计算。如果数组前三个元素相加都大于0说明整个数组最小的三数组合都为正后面不可能凑出和为0直接 break。如果当前数和最大的两个数相加都小于0说明当前数太小和最大值组合都凑不到0直接跳过换下一个数当固定值。内层去重的写法是最容易出错的。找到一组答案后left和right需要同时收缩。收缩之前用两个 while 循环把相同值的指针推到边界。比如数组里有连续好几个 1找到一组解之后left 指向第一个 1while left right and nums[left] nums[left1]会让 left 一直跳到最后一个 1之后再执行一次left 1left 就指向了第一个不是 1 的位置。right 指针的处理方式完全镜像。这套组合拳打完之后就跳过了所有可能形成重复三元组的候选位置。注意内层去重必须放在“找到答案之后”不能在 while 循环开头就无条件去重。如果total ! 0时盲目跳过相同值可能跳过本应成为答案的组合。比如找到total 0之前left 指针指向的相同值可能正是组合所需的元素。3. 两题之上算法套路提炼与实际运用3.1 从两数之和提炼的哈希表模板两数之和是哈希表“边查边存”思路的典型代表。这个思路在力扣上的原型题是 1. 两数之和但它的应用范围远超这一道题。把“边查边存”抽象一下就是遍历过程中把已经看过的信息记录在哈希表里每次面对一个新元素只需要查表判断历史信息是否满足条件。这个模板可以套用到很多题目上比如两数之和的进阶版“两数之和 II - 输入有序数组”因为数组已经排好序反而用双指针更优再比如“和为 K 的子数组”同样是遍历数组把前缀和存入字典每到一个位置查前缀和 - K在不在字典中思路一模一样。我建议每个刷算法题的人都把这个模板刻在脑子里不要只背代码要去理解“记录历史 查询历史”这个动作本质。一旦遇到“找两个历史元素形成某种关系”这类问题第一反应就应该是哈希表。3.2 双指针算法的变式与泛化三数之和用的排序双指针是“对撞指针”的经典案例。对撞指针有一个重要的前置条件——数据在某种维度上是有序的。数组排序后数值大小就是那个维度两个指针分别放在首尾根据当前组合与目标值的大小关系决定是左指针向右移动还是右指针向左移动。每次移动都剔除大量无效组合所以总时间复杂度是 O(n)比起暴力枚举 O(n²) 有质的飞跃。这个模式在力扣里可以泛化出一整个家族最接近的三数之和四数之和验证三角形盛最多水的容器。最接近的三数之和本质上是“在每个固定值下用双指针找最接近目标的组合”只是把“等于0”的判断改成了“更新最小差值”。四数之和则是在三数之和外面再套一层固定循环外层做两次固定内层依旧是双指针。你如果把三数之和彻底写熟了四数之和就是多一层循环的事代码结构几乎完全复用。3.3 刷题学习的路径建议拿我自己刷题的经验来说不建议一上来就抱着“我背会了”的心态去处理这两道题。更好的做法是分三遍去刷。第一遍先想暴力解把暴力解代码跑通确确实实感受到“它有多慢”。第二遍分析暴力解里哪个操作是性能瓶颈思考用什么数据结构或策略能优化它推导出最优解。第三遍不看题解凭记忆和理解把最优解写出来再对照标准答案检查细节。这三遍下来这两道题基本就真正变成你自己的东西了而不是只有一道题的影子。等你后面遇到变体题能自然而然地调用这套思路才算是真的吃透了。4. 常见问题与排查技巧实录4.1 两数之和的边界与陷阱两数之和有两类常见错误值得单独拿出来讲。第一类是“自己匹配自己”。比如nums [3, 3]target 6如果代码写成先存后查那么在遍历第一个 3 时字典里已经存入了索引 0第二个 3 来临时会直接查到字典里刚刚存进去的第一个 3返回[0, 1]结果是正确的。但如果数组是nums [3]target 6先存后查时遍历到唯一的那个 3 就会查到它自己返回[0, 0]这就是错误答案。这也是为什么强调“先查再存”顺序不能乱。它拦截的正是这种“当前元素自己配自己”的场景。第二类是“没有结果返回什么”。题目保证一定有解所以一般不需要特殊处理。但如果你在本地自测或者扩展题目用代码里保留一个兜底返回[]是好习惯。另外题目问的是下标千万别写成返回值本身。我看到过很多新手在本地把两数之和改成返回元素值来测试结果兴致冲冲提交力扣发现全错就是没注意题目要求和自测逻辑之间的差异。4.2 三数之和的去重死循环三数之和最常见的报错不是超时而是结果里有重复三元组。我在网上帮人看代码的时候几乎每一份出错的代码都栽在同一个地方去重逻辑放错位置或者去重时指针移动逻辑写错。我遇到过一个特别典型的错误写法while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1这段去重放在total 0的 if 块外面导致一个奇怪的现象当total 0时左指针遇到相同值会直接跳过看似在加速但跳过的那个位置可能正是当前组合需要的值。举个例子假设固定值是 -2剩余区间是[1, 1, 2]需要找到两个数和为 2正确结果是[1, 1]。但如果左指针遇到连续相同的 1 直接跳到第二个 1最终左指针和右指针相遇什么也没找到漏解了。正确的做法一定是“找到答案再去重没找到答案就按大小关系正常移动指针”。这个顺序是死规矩没有任何讨价还价的余地。4.3 Python3 刷题的环境与效率技巧聊到 Python3我顺便分享几个刷算法题时能提升体验的小技巧。第一个是关于 sort 方法的nums.sort()是原地排序会改变原数组不会产生新的列表sorted(nums)则是返回一个新列表不改动原数组。在三数之和里我们不需要保留原数组顺序所以用nums.sort()就行省内存也更快。但在一些需要保留原序的场景里用sorted()才是安全的别搞混。第二个是判断元素是否存在时尽量用if complement in seen不要用try-except配合KeyError去处理。虽然后者在一些极端情况下性能更优但会牺牲代码可读性刷题阶段清晰比微优化重要得多。第三个是用bisect模块处理有序数组。如果你在有序数组里做二分查找Python3 自带的bisect_left比手写二分快得多还有一个额外的好处是它自带边界检查逻辑。不过在三数之和这种题里双指针本身已经够快了不需要额外用 bisect。4.4 本地自测与在线判题的小建议我建议刷题时一定要在本地建一个专门的测试目录把力扣的示例输入复制下来写成 pytest 或简单的if __name__ __main__自测脚本。不要只在力扣的网页编辑器里测试那个编辑器虽然方便但补全功能弱而且调试信息不够直观出错时很难定位。我的习惯是先用题目给的官方示例测试一遍然后自己再加三种边界用例空数组、全部元素相同、只有一个元素三种情况。对三数之和还要额外加两个用例纯负数数组和纯正数数组验证剪枝逻辑是否正常工作。这些用例放在本地跑一旦发现输出不符合预期直接 print 关键变量就能快速定位问题。比如在调试三数之和时我经常会在left和right移动的地方加 print把每次移动前后的下标和值打出来看是不是真的跳过了预期位置。很多“逻辑没问题但结果错误”的案例靠这一步就能快速锁定原因。5. 刷题之外从这两道题延伸出去的思考两数之和和三数之和分量不在于题目本身有多难而在于它们代表了两大类最基础的算法思维哈希表查表法和排序双指针法。这两类思维几乎是所有进阶算法题的基石。哈希表查表法的本质是空间换时间用一个额外的线性存储结构把查找操作从 O(n) 优化到 O(1)。这个思维延伸到很多领域——比如在处理字符串重复字符、图遍历中的访问标记、动态规划中的状态记录时哈希表的“记录历史信息”作用都是一以贯之的。双指针法的本质则是利用单调性减少无效枚举在一个有序序列里左右指针交替移动每次决策剪掉一批显然不成立的组合把暴力搜索的指数级空间压缩到线性扫一遍。我个人在实际刷题中的体会是这两道题最值得花时间的地方不是记住代码模板而是亲手走一遍“暴力解到优化解”的推导过程。这个过程能训练一种很关键的能力当面对一道新题时先定位问题的瓶颈再选择合适的数据结构或策略去突破它。这种能力一旦形成应付算法面试也好日常写代码时的性能优化也好都会顺手很多。最后再分享一个小技巧刷这两道题的时候建议尝试用 Python3 的本地调试环境多写几遍一遍比一遍快直到能在五分钟内正确写出两数之和、十分钟内正确写出三数之和。这个过程不仅是在练手速更是在帮大脑固化解题路径。等这种“条件反射”建立起来之后再去刷它的各类变体题你会明显感觉到知识迁移变得顺滑很多那种“背题解遇到新题就懵”的困境自然就不存在了。
两数之和与三数之和的核心：哈希表与双指针
两数之和、三数之和这两道题在国内外的算法刷题榜单上常年霸榜。尤其是两数之和基本上所有人刷力扣的第一题就是它。坦白说我一开始刷这两道题的时候也是背题解过来的——两数之和用哈希表三数之和排序加双指针背得滚瓜烂熟但换一道变体题就当场懵住。后来刷得多了才想明白一个事这两道题属于“套路型题目”套路背后是两种极其重要的基础算法思维——查表法与双指针收缩。把它们彻底吃透性价比极高你后面刷四数之和、最接近的三数之和、和为定值的子数组这类题都会轻松很多。这篇笔记我按自己的复盘方式重新整理了一遍从暴力思路推导到最优解每一步都说清楚“为什么要这么写”Python3代码直接放在对应的解析后面。适合刚刷完数组基础、准备系统性学习算法题的朋友也适合准备面试前快速过一遍经典模板的求职党。1. 两数之和从暴力枚举到哈希表的思维跃迁1.1 先看清题目到底在问什么题目描述很简单给定一个整数数组nums和一个整数目标值target请在数组中找出和为目标值的那两个整数并返回它们的数组下标。这里有两个容易忽略的细节一是返回的是下标不是元素本身二是每种输入只会对应一个答案但数组里同一个元素不能重复使用。第一点决定了我们不能直接排序后用双指针因为排序会打乱下标关系第二点则天然迎合了“边查边存”的哈希表思路。我第一次做这道题时第一反应就是双层循环固定第一个数往后遍历找有没有target - nums[i]。这个思路确实能过测试但效率太差了。按最坏情况算一个长度为 n 的数组需要比较约n*(n-1)/2次当 n 到 10000 时直接就是近五千万次比较本地跑还能忍放到判题机上基本就是超时边缘。暴力解法不是没有价值它是我们推导更优解法的起点。把暴力解的核心逻辑抽象出来——找到“目标数”和“当前数”的配对关系你会发现真正的性能瓶颈在于每次查找target - nums[i]都是在剩下的数组里线性扫描这个“查找”操作是 O(n) 的。如果能把这个 O(n) 的查找变成 O(1)那总复杂度就能从 O(n²) 降到 O(n)。1.2 哈希表为什么是更优解把查找变成 O(1)最直接的工具就是哈希表也就是 Python3 里的字典dict。字典的底层是哈希表结构平均增删查操作都是 O(1) 时间复杂度。用字典解题的核心思路是“边遍历、边记录、边查找”我们每遍历到一个新元素nums[i]就去字典里查有没有target - nums[i]。如果存在说明之前某个下标对应的值正好和当前值互补那就直接得出答案如果不存在就把当前元素的值和下标存进字典留给后面匹配。这种做法的精妙之处在于它天然保证了“同一个元素不会重复使用”因为我们是先查字典再往字典里存入当前元素。也就是说当遍历到某个元素时字典里存的只有当前元素之前出现过的元素当前元素还没有被放进去自然不存在自我匹配的问题。我们拿一个简单例子走一遍流程。假设nums [2, 7, 11, 15]target 9初始化字典seen {}遍历到2查9-27不在字典中存入{2: 0}遍历到7查9-72正好在字典中键2对应的值是索引0返回[0, 1]整个过程只遍历了一次数组时间复杂度 O(n)额外使用了一个字典存储数据空间复杂度也是 O(n)。1.3 两数之和的Python3标准写法def two_sum(nums, target): seen {} for i, num in enumerate(nums): complement target - num if complement in seen: return [seen[complement], i] seen[num] i return []这套代码是刷题圈流传最广的模板看起来极简但有几个细节值得反复咀嚼。第一个细节enumerate的用法。它同时拿到下标和元素值比手写for i in range(len(nums))更简洁也更符合 Python3 的惯用法。第二个细节判断用complement in seen而不是complement in seen.keys()后者在 Python3 里会多一层包装调用虽然差距很小但刷题时养成绩优习惯没坏处。第三个细节先查再存。顺序一旦调反遇到重复元素时可能返回错误结果。注意如果题目改成“返回元素值本身”那用单纯的哈希集合set就够了不需要存下标。但本题是返回下标所以必须用字典来存“值到索引”的映射关系。2. 三数之和排序双指针把 O(n³) 压到 O(n²)2.1 为什么不能直接套两数之和的哈希法三数之和的要求是给定数组nums判断数组中是否存在三个元素 a、b、c使得a b c 0返回所有满足条件且不重复的三元组。看到“三数之和是两数之和的升级版”很多人的第一反应是在三数之和里套一层循环固定第一个数剩下两个数用两数之和的哈希法来找不就行了吗这个方法理论上可行但有一个极其致命的痛点——去重非常麻烦。两数之和不用去重是因为题目保证了答案唯一。但三数之和要返回所有不重复的三元组用哈希法实现去重要么先把三元组排序再放进 set要么用复杂的组合条件去判断是否出现过。前者需要大量的哈希计算和存储后者容易把判断条件写得漏洞百出。而且哈希法在处理“返回所有结果”的遍历路径时不够自然代码写出来又长又绕。排序加双指针就用一种非常优雅的方式消解了这个问题先把数组排好序让相同的元素紧挨在一起这样在移动指针时只要跳过相邻的相同元素就能天然避免重复三元组无需额外的 set。这是三数之和这道题背后真正值得学习的思维拐点——用有序性换取去重的便捷性。2.2 排序双指针的推导过程排序双指针的完整推导我习惯分成三个层次去理解。第一个层次是“固定一个数转化为两数之和”。我们在外层循环固定一个数nums[i]问题就变成了在剩下的数组区间[i1, n-1]中找到两个数和等于-nums[i]。这一步把三数问题降维成了两数问题。第二个层次是“双指针在一段有序区间里找两数之和”。因为数组已经排序区间内的元素是从小到大排列的。我们在区间最左端放一个指针left i1最右端放right n-1。计算sum nums[i] nums[left] nums[right]然后根据 sum 与 0 的关系调整指针如果sum 0找到了一个合法三元组记录下来同时移动左右指针继续寻找下一种组合如果sum 0说明当前的三个数之和偏小需要把指针往更大的方向移动也就是left 1如果sum 0说明偏大把right - 1这里需要理解的关键是为什么移动指针就能保证不漏解因为数组有序left往右移动意味着和增大right往左移动意味着和减小这种单调性保证了我们枚举的所有和有明确的走向不需要盲目的暴力搜索。每做一次判断就排除掉一整行或一整列的无效组合这是双指针高效的本质。第三个层次是“去重逻辑”。去重有两个位置外层固定的数要去重内层找到答案后的指针移动也要去重。外层去重很好理解固定的第一个数相同后面找出的所有组合一定相同简称“同一位置重复无意义”。内层去重则是当nums[left]和nums[left1]相同时左指针直接跳到最后一个相同的值右指针同理。这个去重的写法是整道题最容易写错的地方后面我会专门展开说。2.3 三数之和的Python3标准写法def three_sum(nums): nums.sort() n len(nums) result [] for i in range(n - 2): # 外层去重 if i 0 and nums[i] nums[i - 1]: continue # 剪枝最小的三个数都大于0后面不可能有解 if nums[i] nums[i 1] nums[i 2] 0: break # 剪枝当前数加上最大的两个数都小于0当前数太小换下一个 if nums[i] nums[n - 1] nums[n - 2] 0: continue left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: 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 total 0: left 1 else: right - 1 return result这套代码我反复手写了很多遍越写越觉得里面每个判断都有讲究。先看外层去重的写法if i 0 and nums[i] nums[i - 1]。这里必须是nums[i] nums[i-1]不能是nums[i] nums[i1]。原因很微妙如果用nums[i] nums[i1]会直接把当前轮次跳过导致漏掉[-1, -1, 2]这种情况因为第一个 -1 和第二个 -1 相邻用后向比较会把第一个 -1 直接判为重复而事实上第一个 -1 是有用的。再看剪枝的两个判断这是性能优化技巧不是必写代码但写上之后能避免大量无效计算。如果数组前三个元素相加都大于0说明整个数组最小的三数组合都为正后面不可能凑出和为0直接 break。如果当前数和最大的两个数相加都小于0说明当前数太小和最大值组合都凑不到0直接跳过换下一个数当固定值。内层去重的写法是最容易出错的。找到一组答案后left和right需要同时收缩。收缩之前用两个 while 循环把相同值的指针推到边界。比如数组里有连续好几个 1找到一组解之后left 指向第一个 1while left right and nums[left] nums[left1]会让 left 一直跳到最后一个 1之后再执行一次left 1left 就指向了第一个不是 1 的位置。right 指针的处理方式完全镜像。这套组合拳打完之后就跳过了所有可能形成重复三元组的候选位置。注意内层去重必须放在“找到答案之后”不能在 while 循环开头就无条件去重。如果total ! 0时盲目跳过相同值可能跳过本应成为答案的组合。比如找到total 0之前left 指针指向的相同值可能正是组合所需的元素。3. 两题之上算法套路提炼与实际运用3.1 从两数之和提炼的哈希表模板两数之和是哈希表“边查边存”思路的典型代表。这个思路在力扣上的原型题是 1. 两数之和但它的应用范围远超这一道题。把“边查边存”抽象一下就是遍历过程中把已经看过的信息记录在哈希表里每次面对一个新元素只需要查表判断历史信息是否满足条件。这个模板可以套用到很多题目上比如两数之和的进阶版“两数之和 II - 输入有序数组”因为数组已经排好序反而用双指针更优再比如“和为 K 的子数组”同样是遍历数组把前缀和存入字典每到一个位置查前缀和 - K在不在字典中思路一模一样。我建议每个刷算法题的人都把这个模板刻在脑子里不要只背代码要去理解“记录历史 查询历史”这个动作本质。一旦遇到“找两个历史元素形成某种关系”这类问题第一反应就应该是哈希表。3.2 双指针算法的变式与泛化三数之和用的排序双指针是“对撞指针”的经典案例。对撞指针有一个重要的前置条件——数据在某种维度上是有序的。数组排序后数值大小就是那个维度两个指针分别放在首尾根据当前组合与目标值的大小关系决定是左指针向右移动还是右指针向左移动。每次移动都剔除大量无效组合所以总时间复杂度是 O(n)比起暴力枚举 O(n²) 有质的飞跃。这个模式在力扣里可以泛化出一整个家族最接近的三数之和四数之和验证三角形盛最多水的容器。最接近的三数之和本质上是“在每个固定值下用双指针找最接近目标的组合”只是把“等于0”的判断改成了“更新最小差值”。四数之和则是在三数之和外面再套一层固定循环外层做两次固定内层依旧是双指针。你如果把三数之和彻底写熟了四数之和就是多一层循环的事代码结构几乎完全复用。3.3 刷题学习的路径建议拿我自己刷题的经验来说不建议一上来就抱着“我背会了”的心态去处理这两道题。更好的做法是分三遍去刷。第一遍先想暴力解把暴力解代码跑通确确实实感受到“它有多慢”。第二遍分析暴力解里哪个操作是性能瓶颈思考用什么数据结构或策略能优化它推导出最优解。第三遍不看题解凭记忆和理解把最优解写出来再对照标准答案检查细节。这三遍下来这两道题基本就真正变成你自己的东西了而不是只有一道题的影子。等你后面遇到变体题能自然而然地调用这套思路才算是真的吃透了。4. 常见问题与排查技巧实录4.1 两数之和的边界与陷阱两数之和有两类常见错误值得单独拿出来讲。第一类是“自己匹配自己”。比如nums [3, 3]target 6如果代码写成先存后查那么在遍历第一个 3 时字典里已经存入了索引 0第二个 3 来临时会直接查到字典里刚刚存进去的第一个 3返回[0, 1]结果是正确的。但如果数组是nums [3]target 6先存后查时遍历到唯一的那个 3 就会查到它自己返回[0, 0]这就是错误答案。这也是为什么强调“先查再存”顺序不能乱。它拦截的正是这种“当前元素自己配自己”的场景。第二类是“没有结果返回什么”。题目保证一定有解所以一般不需要特殊处理。但如果你在本地自测或者扩展题目用代码里保留一个兜底返回[]是好习惯。另外题目问的是下标千万别写成返回值本身。我看到过很多新手在本地把两数之和改成返回元素值来测试结果兴致冲冲提交力扣发现全错就是没注意题目要求和自测逻辑之间的差异。4.2 三数之和的去重死循环三数之和最常见的报错不是超时而是结果里有重复三元组。我在网上帮人看代码的时候几乎每一份出错的代码都栽在同一个地方去重逻辑放错位置或者去重时指针移动逻辑写错。我遇到过一个特别典型的错误写法while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1这段去重放在total 0的 if 块外面导致一个奇怪的现象当total 0时左指针遇到相同值会直接跳过看似在加速但跳过的那个位置可能正是当前组合需要的值。举个例子假设固定值是 -2剩余区间是[1, 1, 2]需要找到两个数和为 2正确结果是[1, 1]。但如果左指针遇到连续相同的 1 直接跳到第二个 1最终左指针和右指针相遇什么也没找到漏解了。正确的做法一定是“找到答案再去重没找到答案就按大小关系正常移动指针”。这个顺序是死规矩没有任何讨价还价的余地。4.3 Python3 刷题的环境与效率技巧聊到 Python3我顺便分享几个刷算法题时能提升体验的小技巧。第一个是关于 sort 方法的nums.sort()是原地排序会改变原数组不会产生新的列表sorted(nums)则是返回一个新列表不改动原数组。在三数之和里我们不需要保留原数组顺序所以用nums.sort()就行省内存也更快。但在一些需要保留原序的场景里用sorted()才是安全的别搞混。第二个是判断元素是否存在时尽量用if complement in seen不要用try-except配合KeyError去处理。虽然后者在一些极端情况下性能更优但会牺牲代码可读性刷题阶段清晰比微优化重要得多。第三个是用bisect模块处理有序数组。如果你在有序数组里做二分查找Python3 自带的bisect_left比手写二分快得多还有一个额外的好处是它自带边界检查逻辑。不过在三数之和这种题里双指针本身已经够快了不需要额外用 bisect。4.4 本地自测与在线判题的小建议我建议刷题时一定要在本地建一个专门的测试目录把力扣的示例输入复制下来写成 pytest 或简单的if __name__ __main__自测脚本。不要只在力扣的网页编辑器里测试那个编辑器虽然方便但补全功能弱而且调试信息不够直观出错时很难定位。我的习惯是先用题目给的官方示例测试一遍然后自己再加三种边界用例空数组、全部元素相同、只有一个元素三种情况。对三数之和还要额外加两个用例纯负数数组和纯正数数组验证剪枝逻辑是否正常工作。这些用例放在本地跑一旦发现输出不符合预期直接 print 关键变量就能快速定位问题。比如在调试三数之和时我经常会在left和right移动的地方加 print把每次移动前后的下标和值打出来看是不是真的跳过了预期位置。很多“逻辑没问题但结果错误”的案例靠这一步就能快速锁定原因。5. 刷题之外从这两道题延伸出去的思考两数之和和三数之和分量不在于题目本身有多难而在于它们代表了两大类最基础的算法思维哈希表查表法和排序双指针法。这两类思维几乎是所有进阶算法题的基石。哈希表查表法的本质是空间换时间用一个额外的线性存储结构把查找操作从 O(n) 优化到 O(1)。这个思维延伸到很多领域——比如在处理字符串重复字符、图遍历中的访问标记、动态规划中的状态记录时哈希表的“记录历史信息”作用都是一以贯之的。双指针法的本质则是利用单调性减少无效枚举在一个有序序列里左右指针交替移动每次决策剪掉一批显然不成立的组合把暴力搜索的指数级空间压缩到线性扫一遍。我个人在实际刷题中的体会是这两道题最值得花时间的地方不是记住代码模板而是亲手走一遍“暴力解到优化解”的推导过程。这个过程能训练一种很关键的能力当面对一道新题时先定位问题的瓶颈再选择合适的数据结构或策略去突破它。这种能力一旦形成应付算法面试也好日常写代码时的性能优化也好都会顺手很多。最后再分享一个小技巧刷这两道题的时候建议尝试用 Python3 的本地调试环境多写几遍一遍比一遍快直到能在五分钟内正确写出两数之和、十分钟内正确写出三数之和。这个过程不仅是在练手速更是在帮大脑固化解题路径。等这种“条件反射”建立起来之后再去刷它的各类变体题你会明显感觉到知识迁移变得顺滑很多那种“背题解遇到新题就懵”的困境自然就不存在了。
