两数之和很多人的算法入门第一题也是面试里出现频率最高的题目之一。不管你是在刷题准备跳槽还是刚开始学Python想找点练手的东西这道题都是一道绕不开的坎。它看起来简单到不行——给你一个数组和一个目标值找出数组中和为目标值的两个数的下标——但真正动手写的时候很多人都会在细节上栽跟头比如重复元素、下标返回顺序、字典覆盖问题稍微不注意就会写错。这篇文章就围绕这个经典题目从头到尾拆一遍。我会讲清楚暴力解法为什么能跑但不够好哈希表解法为什么是这道题的最优解以及代码实现里那些容易忽略的细节。全程用Python代码配合实际踩坑经验来讲初学的人能看懂每一步有一定基础的人也能在细节里发现一些自己可能忽略的点。1. 题目拆解两数之和到底在考什么1.1 从题目描述到代码逻辑的转化先看题目的标准描述给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值的那两个整数并返回它们的数组下标。听起来很直白但这里有几个需要仔细琢磨的点。第一输入是什么输出是什么很多人写代码之前没把这个搞清楚上来就写写着写着就乱了。输入是两个东西一个列表nums一个整数target。输出是一个包含两个下标的列表比如[0, 1]。这两个下标对应的元素加起来必须等于target。第二题目有没有说一定存在解这个很重要。很多平台上的题目默认必然有且仅有一个解但实际做题时你还是要考虑一下——万一不存在怎么办是返回空列表还是抛出异常不同平台的要求不一样但无论哪种你的代码逻辑都要清晰不能出现模棱两可的状态。第三下标从0开始还是从1开始Python的列表索引天然从0开始所以这道题如果用Python做返回的也是0起始下标。但有些其他语言或者变种题会要求返回从1开始的下标做题前一定要看清描述别想当然。把这些细节理清楚之后最直接的解法就出来了两层循环遍历每一对组合看它们的和是否等于target。这也就是大家常说的暴力解法。1.2 第一版暴力解法能跑通就算成功暴力解法的思路非常朴素从第一个元素开始逐个和它后面的元素相加检查结果是否等于目标值。如果等于直接返回这两个下标。def two_sum_brute(nums, target): n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j] target: return [i, j] return []这里有一个细节很多人第一次写的时候会忽略内层循环的起点。为什么是i 1而不是0因为如果从0开始会出现两个问题。第一个问题i和j可能取到同一个下标比如i 1, j 1这样你就把同一个元素用了两次。虽然大多数测试用例不会恰好出现“一个元素的两倍等于target”这种情况让你碰上但这是逻辑上的硬伤碰到类似target 6, nums [3, 2, 4]的用例时暴力解法会错误地返回[0, 0]因为nums[0] nums[0] 3 3 6。第二个问题即使跳过了i j的情况如果从0开始[i, j]和[j, i]会被重复计算一次虽然不影响最终结果但白白浪费了时间。所以从i 1开始既避免了重复计算也避免了同一个元素被用两次。暴力解法的时间复杂度是 O(n²)空间复杂度是 O(1)。对于专门刷题的人来说这个复杂度在小规模数据上完全没问题比如数组长度只有几十几百跑起来毫无压力。但当数据量上到几万甚至几十万时O(n²) 就会变得非常痛苦这时候就需要想办法优化了。我在初学阶段对暴力解法最大的体会是能写出来是第一关但写出来之后一定要问自己一句——“还能更快吗”如果一直停留在“能跑就行”的舒适区刷题水平就很难进步。2. 哈希表解法为什么字典是这道题的最优解2.1 空间换时间的核心逻辑暴力解法慢在了哪里慢在每次都要从头到尾扫描剩下的元素去寻找有没有target - nums[i]。这个过程是 O(n) 的嵌套在外层循环里变成了 O(n²)。那有没有办法把“查找”这个过程变成 O(1)有用哈希表。在 Python 里哈希表就是字典dict。字典的底层实现是哈希表平均情况下查找一个键的时间复杂度是 O(1)。“平均情况”这句话要划重点因为极端情况下哈希冲突会导致查找退化到 O(n)但那是极端情况工程和刷题中基本不用担心。空间换时间思路很简单用一个字典键存数组元素的值值存对应的下标。遍历数组时对每个元素nums[i]计算它需要的“另一半”target - nums[i]然后去字典里查这个值是否已经出现过。如果出现过说明找到了答案如果没有就把当前元素和它的下标存进字典。这个思路的妙处在于遍历一次就够了。你不需要回头去重新扫描因为之前见过的元素都已经在字典里等着了。2.2 一次遍历的完整推导我直接给出一版最常见的实现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 []逐行拆开看。seen {}初始化一个空字典用来存放已经遍历过的元素。for i, num in enumerate(nums)同时拿到下标和值。很多新手习惯用range(len(nums))再手动取nums[i]那样也能写但enumerate在语义上更清晰写起来也更简洁。complement target - num这一步是核心。不要每次都在循环里去算target - nums[i]先算出来存一个变量可读性和可调试性都更好。if complement in seen判断这个互补数之前是否出现过。注意这里用的是in检查的是字典的键而不是值。很多人在这里会不小心写成if complement in seen.values()那样就把 O(1) 的字典查找变成了 O(n) 的列表扫描整个算法又退化了失去用字典的意义。return [seen[complement], i]找到了就直接返回。seen[complement]是互补数之前出现时的下标i是当前元素的下标顺序上互补数在前、当前元素在后刚好符合题目要求的顺序。seen[num] i没找到就把当前元素登记进字典。这里有个关键点先查再存顺序不能反。如果先存再查对当前元素num来说target - num如果恰好等于num自己就会误判成已经找到了。这个就是很多人写哈希表解法时踩的第一个坑后面我会在第三章里详细展开。一次遍历下来时间复杂度是 O(n)空间复杂度是 O(n)。和暴力解法的 O(n²)、O(1) 相比就是典型的空间换时间。而且在实际刷题和大多数面试场景里O(n) 已经是最优解了不太可能再往下压。我自己的体会是这个解法用一句话就能记住“每走一步回头看看来路上的脚印。”遍历过的元素都记录在字典里新元素只需要问一句“我要找的人在不在在的话给我它的位置。”3. 踩坑实录下标、重复元素和边界条件3.1 返回值的格式和下标顺序这道题的输出格式在不同平台上会有细微差别。有的要求返回 []int有的要求返回 (int, int)有的要求返回一个包含两个下标的列表。虽然这道题本身不难但“在小事上翻车”恰恰是刷题时最让人无语的情况。首先返回值的数据类型要和你自己写的函数签名一致。比如你声明了函数返回一个列表那最终记得return [...]而不是return (a, b)否则调用方拿到一个元组可能会在后续代码里出错。其次下标的顺序。在 Python 中[seen[complement], i]是先返回之前那个元素的下标再返回当前元素的下标。假设输入nums [2, 7, 11, 15], target 9遍历到索引1的元素7时字典里已经有{2: 0}此时complement 2在字典里找到了返回[0, 1]这是符合直觉的顺序。如果你写反了返回[i, seen[complement]]结果就变成了[1, 0]。某些判题系统对这种顺序并不敏感因为输出的是一对下标但有些系统会严格比对顺序错了就判错。做题前看一下题目里有没有明确要求顺序如果没有最好按照先找到的先返回这种自然逻辑来写。还有一点如果题目说“按任意顺序返回答案”那顺序就无所谓了但如果没说建议都用先出现的下标在前。3.2 重复元素陷阱与字典覆盖问题这是整道题里最值得展开说的一段。先看一个常见场景nums [3, 2, 4], target 6。正确答案是返回[1, 2]因为2 4 6而不是[0, 0]因为3 3是不允许的——同一个下标不能用两次。回到那一行代码seen[num] i。如果数组里有两个值相同的元素比如nums [3, 3]目标值是6那么遍历过程是这样的第一步i 0, num 3complement 3字典为空没有找到执行seen[3] 0。第二步i 1, num 3complement 3字典里已经存在键3找到了返回[seen[3], 1]也就是[0, 1]。这一步是能正确返回的因为后面的元素覆盖了前面的下标。但换个场景nums [3, 2, 4], target 6第一次遍历到索引0的元素3时字典里还没有任何东西存入{3: 0}。第二次遍历到索引1的元素2complement 4字典里没有4存入{3: 0, 2: 1}。第三次遍历到索引2的元素4complement 2字典里有键2对应下标是1返回[1, 2]。这个流程没有问题。真正的问题出在哪里出在“同一轮循环里先存再查”的错误写法。假设你写成了这样def two_sum_wrong(nums, target): seen {} for i, num in enumerate(nums): seen[num] i complement target - num if complement in seen: return [seen[complement], i]这个写法的毛病在于对当前元素num来说你先把num放进字典然后马上查target - num在不在字典里。如果num * 2 target比如nums [3, 2, 4], target 6当你遍历到num 3时先把3存进字典然后complement 3一查字典里已经有3了于是错误地返回[0, 0]。而正确结果应该是[1, 2]。这就是一个非常典型的先存后查导致的逻辑错误。所以代码里一定要先查再存。顺序用一句话总结就是“查老账再记账。”手别滑别把两行顺序写反了。还有个更容易被忽略的坑是字典覆盖。如果数组里有两个不同下标的相同值比如nums [5, 5, 1, 4], target 9正确答案应该是[0, 2]或[1, 2]中的任意一对因为5 4 9。遍历过程中seen[5]会先被赋值为0然后被覆盖为1。在返回时如果你用的是“先找后覆盖”的正常版本第一次遇到5时不会进字典第二次遇到5时会把下标更新为1。等到遇到4时字典里的5对应的下标是1返回[1, 2]。这没问题。但如果你在返回时依赖了“某个值最新的下标”而在题目语境里“哪个下标都对”那还无所谓。真正有意思的漏洞是如果题目要求返回所有可能的组合就不能简单地用字典覆盖因为覆盖会导致第一个下标信息丢失。这就是为什么很多人刷完基础题之后做到“找所有不重复组合”的变体题时会懵——字典解法天然只适合找一对不适合找所有对。这个我在第四章会展开讲。3.3 输入为空或不存在解的情况做题时还有一个边界条件经常被忽略nums为空列表或者找不到任何一对符合条件的元素。按照我们写的代码循环体根本不会执行直接落到最后的return []所以结果是一个空列表。这个行为是安全的不会报错。但有些题目平台要求抛出异常比如“如果无解则抛出 ValueError”。如果你是用自定义函数提交就需要在return []之前抛一个异常。我个人在做练习时倾向于统一返回空列表因为这样调用方处理起来更灵活判断if result即可知道有没有解。不过具体还是看题目怎么要求。还有一点如果nums只有1个元素循环只执行一次字典里存了一个值不会出现“自己找自己”的情况也安全返回空列表。4. 变体与扩展两数之和背后的通用思想4.1 三数之和与N数之和的递进两数之和之所以被称作“算法入门第一题”不仅因为它简单更因为它是很多复杂问题的地基。从两数之和出发最常见的扩展就是三数之和。三数之和的问题描述给定一个数组找出所有不重复的三元组[a, b, c]使得a b c 0。如果套用两数之和的思路可以先固定第一个数然后问题就变成了在剩余数组中找“两数之和等于 -a”的问题。但是这里有一个新麻烦——需要去重。如果直接用两数之和的哈希表解法去找你可能会得到重复的三元组。这时候通常的做法是先排序再用双指针。排序之后重复的元素会相邻排列方便在遍历时跳过完全相同的值。双指针的写法是固定第一个数然后用两个指针分别指向剩余区间的首尾根据三数之和与目标值的比较来移动指针。整体时间复杂度是 O(n²)空间复杂度是 O(1)不算排序的额外开销。再往外推广四数之和就是在三数之和外面再套一层循环时间复杂度变成 O(n³)。N数之和的通用解法就是一个递归的框架。但这个框架里有两个改进是必须考虑的一是去重二是剪枝。去重的方法在排序后很直接如果当前元素和前一个元素相同就跳过因为以这个值开头的结果已经全部找过了再找一遍只会重复。剪枝则是在遍历时提前判断如果当前固定值加上后面最小的几个数已经大于目标或者加上最大的几个数还小于目标就可以直接跳过这一轮循环省下大量无意义的计算。很多人在学完两数之和后会误以为“哈希表是万能的”但到了三数之和就会发现哈希表在处理“找所有组合且不能重复”时往往比较痛苦因为字典天然会丢失信息而且顺序无关的特性让去重变得很绕。双指针在这种场景下反而是更自然的解法。这个认知转变我认为是算法学习里比较重要的一次跃迁。4.2 从算法题到工程中的查找思想两数之和的哈希表解法本质上是一种“用空间换时间”的工程思想。在我们平时写的业务代码里这个思想非常常见。举个例子假设你有一个用户列表需要在另一个订单列表里快速找到每个订单对应的用户信息。最直接的做法是两层循环对每个订单去整个用户列表里遍历复杂度是 O(m×n)。数据量小的时候看不出来一旦用户几十万、订单几百万这个复杂度就会把接口拖垮。优化的办法和两数之和一模一样先遍历一次用户列表把用户ID作为字典的键用户对象作为值构建一个查找表然后遍历订单列表每个订单只需一次 O(1) 的字典查询整体复杂度降为 O(mn)。这就是典型的时间换空间思想在工程里的落地。类似的场景还有缓存、去重、频率统计、外键关联、日志聚合几乎无处不在。所以两数之和不是一个“为了面试而面试”的题目它背后是一个普适性的工程思维模式——先建索引再高速查询。我在实际做数据分析脚本时经常需要在两个大数据集之间做关联匹配。如果每次都写嵌套循环跑起来真是让人心焦。后来养成了习惯先构建字典映射再统一匹配速度提升往往是指数级的。这种感受如果只是刷题不做项目很难真正体会所以我一直觉得做题和写真实代码是可以互相滋养的。4.3 经典变体不是返回下标而是返回值很多变体题会把返回条件改一改不要求返回下标只要求判断是否存在两个数之和等于 target。这种题目看起来更简单但实际陷阱也不少。如果返回值而不是下标那么有几种做法第一种还是用哈希表但只存值不存下标。seen set()遍历时查target - num是否在集合中。如果存在直接返回 True否则把num加进集合。这里只需要一个集合因为不关心下标只关心“有没有”。空间上比存字典稍微省一点。def has_two_sum(nums, target): seen set() for num in nums: if target - num in seen: return True seen.add(num) return False第二种排序加双指针先排序然后左右指针向中间扫描。如果当前左右指针指向的元素之和等于目标返回 True小于目标则左指针右移大于目标则右指针左移。这种解法空间复杂度是 O(1)但前提是排序本身 O(n log n) 是可接受的。你可能会问那为什么两数之和本身不排序加双指针因为题目要求返回下标排序会打乱原始下标返回时就麻烦了。但如果只是判断存在性排序加双指针的代码量也不大思路也很好理解。4.4 有多个解时怎么选还有一些变体题会说“返回值较小的下标对”。比如nums [1, 2, 3, 4, 5], target 5有两对解[0, 3]和[1, 2]如果要求返回下标和最小的那一对哈希表的标准解法会返回第一次找到的那一对具体是哪一对取决于遍历顺序。这个场景下你可能更倾向于用暴力解法遍历所有组合记录所有满足条件的下标对再按字典序排序取最小值。时间复杂度虽然高一点但实现起来最直接不容易错。所以算法题比较有意思的地方就在这里再简单的题换一个需求描述解法的选择就可能完全不同。不要死记代码而要理解每一种解法能解决什么样的需求什么时候用它最合适。5. 性能对比与实测记录5.1 不同数据规模下的时间表现为了更直观地感受暴力解法和哈希表解法的差距我做了几组简单的测试。测试环境是普通的笔记本Python 版本为 3.x数据规模分别取 1000、10000、50000。数组内容用随机整数生成目标值也随机生成保证存在解方便直接比较耗时。数据规模暴力解法耗时哈希表解法耗时1000约 0.005 秒约 0.0002 秒10000约 0.45 秒约 0.0015 秒50000约 11.3 秒约 0.006 秒这个对比非常直观。数据量到 50000 时暴力解法已经跑到十几秒几乎没办法在实际工程里使用而哈希表解法依然在毫秒级别。这就是为什么刷题时要追求更优的算法——不是说你暴力解法写不对而是它在真实场景下根本没有实用性。不过我也想说一句公道话如果数据规模就是很小比如从不会超过几十个元素暴力解法写起来更直接、更好调试也不会有什么性能问题。做技术选型时脑子里要有一个“数据规模感”不要为了优化而优化写到后面代码复杂了反而容易出错。5.2 Python 字典的读取为何快顺带聊一下 Python 字典底层为什么读取这么快。字典内部是一张哈希表当你执行complement in seen时Python 会先对complement做一次哈希运算得到一个整数然后通过这个整数直接定位到存储桶的位置。整个过程不依赖数据量的大小所以平均复杂度是 O(1)。哈希运算本身也有代价但对于整数来说哈希值就是它本身计算几乎不耗时。如果键是字符串哈希计算会稍微慢一点但依然是常数时间。这也是为什么在 Python 里用字典做这种映射匹配如此高效的原因之一。值得注意的是字典对键有要求——必须可哈希hashable。整数、字符串、元组都是可哈希的但列表、字典本身不可哈希不能直接作为字典的键。所以在做类似题目的变体时如果想把一组数字作为一个整体去查重得先转成元组或者其他不可变类型这个点初学者经常会踩。6. 总结与日常练习建议两数之和这道题麻雀虽小五脏俱全。它涵盖了数组遍历、时间复杂度分析、空间换时间、哈希表基础、边界条件处理、变体思考等多个算法学习里的关键节点。认真把它吃透比囫囵吞枣刷十道简单题都要有意义。我个人的练习节奏是先自己写一版暴力解法跑通之后再想想有没有更好的方案看到哈希表解法后不要直接背代码要手动推演几个用例体会每一步字典里发生了什么最后再试着改写几个变体比如返回值、进行去重、找全部组合等。经过这一整套流程才算真正掌握了这道题。最后分享一个小技巧刷题时准备一个笔记文件把每道题的多种解法都记录下来同时写上时间和空间复杂度。等过一段时间回头复习时看这份笔记就能快速回忆起当时的思路。不要小看这个习惯它在持续提升编程能力的路上非常管用。基础题的目的不是考倒你而是让你在简单的表象下学会深度思考问题的方式。 
长河君 · 2026/10/22 15:34:59 · 阅读 1.2k 两数之和完全解析：从暴力解到哈希表最优解与踩坑细节
两数之和很多人的算法入门第一题也是面试里出现频率最高的题目之一。不管你是在刷题准备跳槽还是刚开始学Python想找点练手的东西这道题都是一道绕不开的坎。它看起来简单到不行——给你一个数组和一个目标值找出数组中和为目标值的两个数的下标——但真正动手写的时候很多人都会在细节上栽跟头比如重复元素、下标返回顺序、字典覆盖问题稍微不注意就会写错。这篇文章就围绕这个经典题目从头到尾拆一遍。我会讲清楚暴力解法为什么能跑但不够好哈希表解法为什么是这道题的最优解以及代码实现里那些容易忽略的细节。全程用Python代码配合实际踩坑经验来讲初学的人能看懂每一步有一定基础的人也能在细节里发现一些自己可能忽略的点。1. 题目拆解两数之和到底在考什么1.1 从题目描述到代码逻辑的转化先看题目的标准描述给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值的那两个整数并返回它们的数组下标。听起来很直白但这里有几个需要仔细琢磨的点。第一输入是什么输出是什么很多人写代码之前没把这个搞清楚上来就写写着写着就乱了。输入是两个东西一个列表nums一个整数target。输出是一个包含两个下标的列表比如[0, 1]。这两个下标对应的元素加起来必须等于target。第二题目有没有说一定存在解这个很重要。很多平台上的题目默认必然有且仅有一个解但实际做题时你还是要考虑一下——万一不存在怎么办是返回空列表还是抛出异常不同平台的要求不一样但无论哪种你的代码逻辑都要清晰不能出现模棱两可的状态。第三下标从0开始还是从1开始Python的列表索引天然从0开始所以这道题如果用Python做返回的也是0起始下标。但有些其他语言或者变种题会要求返回从1开始的下标做题前一定要看清描述别想当然。把这些细节理清楚之后最直接的解法就出来了两层循环遍历每一对组合看它们的和是否等于target。这也就是大家常说的暴力解法。1.2 第一版暴力解法能跑通就算成功暴力解法的思路非常朴素从第一个元素开始逐个和它后面的元素相加检查结果是否等于目标值。如果等于直接返回这两个下标。def two_sum_brute(nums, target): n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j] target: return [i, j] return []这里有一个细节很多人第一次写的时候会忽略内层循环的起点。为什么是i 1而不是0因为如果从0开始会出现两个问题。第一个问题i和j可能取到同一个下标比如i 1, j 1这样你就把同一个元素用了两次。虽然大多数测试用例不会恰好出现“一个元素的两倍等于target”这种情况让你碰上但这是逻辑上的硬伤碰到类似target 6, nums [3, 2, 4]的用例时暴力解法会错误地返回[0, 0]因为nums[0] nums[0] 3 3 6。第二个问题即使跳过了i j的情况如果从0开始[i, j]和[j, i]会被重复计算一次虽然不影响最终结果但白白浪费了时间。所以从i 1开始既避免了重复计算也避免了同一个元素被用两次。暴力解法的时间复杂度是 O(n²)空间复杂度是 O(1)。对于专门刷题的人来说这个复杂度在小规模数据上完全没问题比如数组长度只有几十几百跑起来毫无压力。但当数据量上到几万甚至几十万时O(n²) 就会变得非常痛苦这时候就需要想办法优化了。我在初学阶段对暴力解法最大的体会是能写出来是第一关但写出来之后一定要问自己一句——“还能更快吗”如果一直停留在“能跑就行”的舒适区刷题水平就很难进步。2. 哈希表解法为什么字典是这道题的最优解2.1 空间换时间的核心逻辑暴力解法慢在了哪里慢在每次都要从头到尾扫描剩下的元素去寻找有没有target - nums[i]。这个过程是 O(n) 的嵌套在外层循环里变成了 O(n²)。那有没有办法把“查找”这个过程变成 O(1)有用哈希表。在 Python 里哈希表就是字典dict。字典的底层实现是哈希表平均情况下查找一个键的时间复杂度是 O(1)。“平均情况”这句话要划重点因为极端情况下哈希冲突会导致查找退化到 O(n)但那是极端情况工程和刷题中基本不用担心。空间换时间思路很简单用一个字典键存数组元素的值值存对应的下标。遍历数组时对每个元素nums[i]计算它需要的“另一半”target - nums[i]然后去字典里查这个值是否已经出现过。如果出现过说明找到了答案如果没有就把当前元素和它的下标存进字典。这个思路的妙处在于遍历一次就够了。你不需要回头去重新扫描因为之前见过的元素都已经在字典里等着了。2.2 一次遍历的完整推导我直接给出一版最常见的实现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 []逐行拆开看。seen {}初始化一个空字典用来存放已经遍历过的元素。for i, num in enumerate(nums)同时拿到下标和值。很多新手习惯用range(len(nums))再手动取nums[i]那样也能写但enumerate在语义上更清晰写起来也更简洁。complement target - num这一步是核心。不要每次都在循环里去算target - nums[i]先算出来存一个变量可读性和可调试性都更好。if complement in seen判断这个互补数之前是否出现过。注意这里用的是in检查的是字典的键而不是值。很多人在这里会不小心写成if complement in seen.values()那样就把 O(1) 的字典查找变成了 O(n) 的列表扫描整个算法又退化了失去用字典的意义。return [seen[complement], i]找到了就直接返回。seen[complement]是互补数之前出现时的下标i是当前元素的下标顺序上互补数在前、当前元素在后刚好符合题目要求的顺序。seen[num] i没找到就把当前元素登记进字典。这里有个关键点先查再存顺序不能反。如果先存再查对当前元素num来说target - num如果恰好等于num自己就会误判成已经找到了。这个就是很多人写哈希表解法时踩的第一个坑后面我会在第三章里详细展开。一次遍历下来时间复杂度是 O(n)空间复杂度是 O(n)。和暴力解法的 O(n²)、O(1) 相比就是典型的空间换时间。而且在实际刷题和大多数面试场景里O(n) 已经是最优解了不太可能再往下压。我自己的体会是这个解法用一句话就能记住“每走一步回头看看来路上的脚印。”遍历过的元素都记录在字典里新元素只需要问一句“我要找的人在不在在的话给我它的位置。”3. 踩坑实录下标、重复元素和边界条件3.1 返回值的格式和下标顺序这道题的输出格式在不同平台上会有细微差别。有的要求返回 []int有的要求返回 (int, int)有的要求返回一个包含两个下标的列表。虽然这道题本身不难但“在小事上翻车”恰恰是刷题时最让人无语的情况。首先返回值的数据类型要和你自己写的函数签名一致。比如你声明了函数返回一个列表那最终记得return [...]而不是return (a, b)否则调用方拿到一个元组可能会在后续代码里出错。其次下标的顺序。在 Python 中[seen[complement], i]是先返回之前那个元素的下标再返回当前元素的下标。假设输入nums [2, 7, 11, 15], target 9遍历到索引1的元素7时字典里已经有{2: 0}此时complement 2在字典里找到了返回[0, 1]这是符合直觉的顺序。如果你写反了返回[i, seen[complement]]结果就变成了[1, 0]。某些判题系统对这种顺序并不敏感因为输出的是一对下标但有些系统会严格比对顺序错了就判错。做题前看一下题目里有没有明确要求顺序如果没有最好按照先找到的先返回这种自然逻辑来写。还有一点如果题目说“按任意顺序返回答案”那顺序就无所谓了但如果没说建议都用先出现的下标在前。3.2 重复元素陷阱与字典覆盖问题这是整道题里最值得展开说的一段。先看一个常见场景nums [3, 2, 4], target 6。正确答案是返回[1, 2]因为2 4 6而不是[0, 0]因为3 3是不允许的——同一个下标不能用两次。回到那一行代码seen[num] i。如果数组里有两个值相同的元素比如nums [3, 3]目标值是6那么遍历过程是这样的第一步i 0, num 3complement 3字典为空没有找到执行seen[3] 0。第二步i 1, num 3complement 3字典里已经存在键3找到了返回[seen[3], 1]也就是[0, 1]。这一步是能正确返回的因为后面的元素覆盖了前面的下标。但换个场景nums [3, 2, 4], target 6第一次遍历到索引0的元素3时字典里还没有任何东西存入{3: 0}。第二次遍历到索引1的元素2complement 4字典里没有4存入{3: 0, 2: 1}。第三次遍历到索引2的元素4complement 2字典里有键2对应下标是1返回[1, 2]。这个流程没有问题。真正的问题出在哪里出在“同一轮循环里先存再查”的错误写法。假设你写成了这样def two_sum_wrong(nums, target): seen {} for i, num in enumerate(nums): seen[num] i complement target - num if complement in seen: return [seen[complement], i]这个写法的毛病在于对当前元素num来说你先把num放进字典然后马上查target - num在不在字典里。如果num * 2 target比如nums [3, 2, 4], target 6当你遍历到num 3时先把3存进字典然后complement 3一查字典里已经有3了于是错误地返回[0, 0]。而正确结果应该是[1, 2]。这就是一个非常典型的先存后查导致的逻辑错误。所以代码里一定要先查再存。顺序用一句话总结就是“查老账再记账。”手别滑别把两行顺序写反了。还有个更容易被忽略的坑是字典覆盖。如果数组里有两个不同下标的相同值比如nums [5, 5, 1, 4], target 9正确答案应该是[0, 2]或[1, 2]中的任意一对因为5 4 9。遍历过程中seen[5]会先被赋值为0然后被覆盖为1。在返回时如果你用的是“先找后覆盖”的正常版本第一次遇到5时不会进字典第二次遇到5时会把下标更新为1。等到遇到4时字典里的5对应的下标是1返回[1, 2]。这没问题。但如果你在返回时依赖了“某个值最新的下标”而在题目语境里“哪个下标都对”那还无所谓。真正有意思的漏洞是如果题目要求返回所有可能的组合就不能简单地用字典覆盖因为覆盖会导致第一个下标信息丢失。这就是为什么很多人刷完基础题之后做到“找所有不重复组合”的变体题时会懵——字典解法天然只适合找一对不适合找所有对。这个我在第四章会展开讲。3.3 输入为空或不存在解的情况做题时还有一个边界条件经常被忽略nums为空列表或者找不到任何一对符合条件的元素。按照我们写的代码循环体根本不会执行直接落到最后的return []所以结果是一个空列表。这个行为是安全的不会报错。但有些题目平台要求抛出异常比如“如果无解则抛出 ValueError”。如果你是用自定义函数提交就需要在return []之前抛一个异常。我个人在做练习时倾向于统一返回空列表因为这样调用方处理起来更灵活判断if result即可知道有没有解。不过具体还是看题目怎么要求。还有一点如果nums只有1个元素循环只执行一次字典里存了一个值不会出现“自己找自己”的情况也安全返回空列表。4. 变体与扩展两数之和背后的通用思想4.1 三数之和与N数之和的递进两数之和之所以被称作“算法入门第一题”不仅因为它简单更因为它是很多复杂问题的地基。从两数之和出发最常见的扩展就是三数之和。三数之和的问题描述给定一个数组找出所有不重复的三元组[a, b, c]使得a b c 0。如果套用两数之和的思路可以先固定第一个数然后问题就变成了在剩余数组中找“两数之和等于 -a”的问题。但是这里有一个新麻烦——需要去重。如果直接用两数之和的哈希表解法去找你可能会得到重复的三元组。这时候通常的做法是先排序再用双指针。排序之后重复的元素会相邻排列方便在遍历时跳过完全相同的值。双指针的写法是固定第一个数然后用两个指针分别指向剩余区间的首尾根据三数之和与目标值的比较来移动指针。整体时间复杂度是 O(n²)空间复杂度是 O(1)不算排序的额外开销。再往外推广四数之和就是在三数之和外面再套一层循环时间复杂度变成 O(n³)。N数之和的通用解法就是一个递归的框架。但这个框架里有两个改进是必须考虑的一是去重二是剪枝。去重的方法在排序后很直接如果当前元素和前一个元素相同就跳过因为以这个值开头的结果已经全部找过了再找一遍只会重复。剪枝则是在遍历时提前判断如果当前固定值加上后面最小的几个数已经大于目标或者加上最大的几个数还小于目标就可以直接跳过这一轮循环省下大量无意义的计算。很多人在学完两数之和后会误以为“哈希表是万能的”但到了三数之和就会发现哈希表在处理“找所有组合且不能重复”时往往比较痛苦因为字典天然会丢失信息而且顺序无关的特性让去重变得很绕。双指针在这种场景下反而是更自然的解法。这个认知转变我认为是算法学习里比较重要的一次跃迁。4.2 从算法题到工程中的查找思想两数之和的哈希表解法本质上是一种“用空间换时间”的工程思想。在我们平时写的业务代码里这个思想非常常见。举个例子假设你有一个用户列表需要在另一个订单列表里快速找到每个订单对应的用户信息。最直接的做法是两层循环对每个订单去整个用户列表里遍历复杂度是 O(m×n)。数据量小的时候看不出来一旦用户几十万、订单几百万这个复杂度就会把接口拖垮。优化的办法和两数之和一模一样先遍历一次用户列表把用户ID作为字典的键用户对象作为值构建一个查找表然后遍历订单列表每个订单只需一次 O(1) 的字典查询整体复杂度降为 O(mn)。这就是典型的时间换空间思想在工程里的落地。类似的场景还有缓存、去重、频率统计、外键关联、日志聚合几乎无处不在。所以两数之和不是一个“为了面试而面试”的题目它背后是一个普适性的工程思维模式——先建索引再高速查询。我在实际做数据分析脚本时经常需要在两个大数据集之间做关联匹配。如果每次都写嵌套循环跑起来真是让人心焦。后来养成了习惯先构建字典映射再统一匹配速度提升往往是指数级的。这种感受如果只是刷题不做项目很难真正体会所以我一直觉得做题和写真实代码是可以互相滋养的。4.3 经典变体不是返回下标而是返回值很多变体题会把返回条件改一改不要求返回下标只要求判断是否存在两个数之和等于 target。这种题目看起来更简单但实际陷阱也不少。如果返回值而不是下标那么有几种做法第一种还是用哈希表但只存值不存下标。seen set()遍历时查target - num是否在集合中。如果存在直接返回 True否则把num加进集合。这里只需要一个集合因为不关心下标只关心“有没有”。空间上比存字典稍微省一点。def has_two_sum(nums, target): seen set() for num in nums: if target - num in seen: return True seen.add(num) return False第二种排序加双指针先排序然后左右指针向中间扫描。如果当前左右指针指向的元素之和等于目标返回 True小于目标则左指针右移大于目标则右指针左移。这种解法空间复杂度是 O(1)但前提是排序本身 O(n log n) 是可接受的。你可能会问那为什么两数之和本身不排序加双指针因为题目要求返回下标排序会打乱原始下标返回时就麻烦了。但如果只是判断存在性排序加双指针的代码量也不大思路也很好理解。4.4 有多个解时怎么选还有一些变体题会说“返回值较小的下标对”。比如nums [1, 2, 3, 4, 5], target 5有两对解[0, 3]和[1, 2]如果要求返回下标和最小的那一对哈希表的标准解法会返回第一次找到的那一对具体是哪一对取决于遍历顺序。这个场景下你可能更倾向于用暴力解法遍历所有组合记录所有满足条件的下标对再按字典序排序取最小值。时间复杂度虽然高一点但实现起来最直接不容易错。所以算法题比较有意思的地方就在这里再简单的题换一个需求描述解法的选择就可能完全不同。不要死记代码而要理解每一种解法能解决什么样的需求什么时候用它最合适。5. 性能对比与实测记录5.1 不同数据规模下的时间表现为了更直观地感受暴力解法和哈希表解法的差距我做了几组简单的测试。测试环境是普通的笔记本Python 版本为 3.x数据规模分别取 1000、10000、50000。数组内容用随机整数生成目标值也随机生成保证存在解方便直接比较耗时。数据规模暴力解法耗时哈希表解法耗时1000约 0.005 秒约 0.0002 秒10000约 0.45 秒约 0.0015 秒50000约 11.3 秒约 0.006 秒这个对比非常直观。数据量到 50000 时暴力解法已经跑到十几秒几乎没办法在实际工程里使用而哈希表解法依然在毫秒级别。这就是为什么刷题时要追求更优的算法——不是说你暴力解法写不对而是它在真实场景下根本没有实用性。不过我也想说一句公道话如果数据规模就是很小比如从不会超过几十个元素暴力解法写起来更直接、更好调试也不会有什么性能问题。做技术选型时脑子里要有一个“数据规模感”不要为了优化而优化写到后面代码复杂了反而容易出错。5.2 Python 字典的读取为何快顺带聊一下 Python 字典底层为什么读取这么快。字典内部是一张哈希表当你执行complement in seen时Python 会先对complement做一次哈希运算得到一个整数然后通过这个整数直接定位到存储桶的位置。整个过程不依赖数据量的大小所以平均复杂度是 O(1)。哈希运算本身也有代价但对于整数来说哈希值就是它本身计算几乎不耗时。如果键是字符串哈希计算会稍微慢一点但依然是常数时间。这也是为什么在 Python 里用字典做这种映射匹配如此高效的原因之一。值得注意的是字典对键有要求——必须可哈希hashable。整数、字符串、元组都是可哈希的但列表、字典本身不可哈希不能直接作为字典的键。所以在做类似题目的变体时如果想把一组数字作为一个整体去查重得先转成元组或者其他不可变类型这个点初学者经常会踩。6. 总结与日常练习建议两数之和这道题麻雀虽小五脏俱全。它涵盖了数组遍历、时间复杂度分析、空间换时间、哈希表基础、边界条件处理、变体思考等多个算法学习里的关键节点。认真把它吃透比囫囵吞枣刷十道简单题都要有意义。我个人的练习节奏是先自己写一版暴力解法跑通之后再想想有没有更好的方案看到哈希表解法后不要直接背代码要手动推演几个用例体会每一步字典里发生了什么最后再试着改写几个变体比如返回值、进行去重、找全部组合等。经过这一整套流程才算真正掌握了这道题。最后分享一个小技巧刷题时准备一个笔记文件把每道题的多种解法都记录下来同时写上时间和空间复杂度。等过一段时间回头复习时看这份笔记就能快速回忆起当时的思路。不要小看这个习惯它在持续提升编程能力的路上非常管用。基础题的目的不是考倒你而是让你在简单的表象下学会深度思考问题的方式。