第一次遇到“两数之和”是在一场技术面试的现场不过我不是面试者而是坐在对面听候选人讲思路的面试官。当时候选人用了不到五分钟写了一个双重循环然后抬头说“做完了”。我让他打开终端自己生成一个长度为十万的随机数组然后跑一下那段代码。他连续敲了几次回车程序都没在预期时间内返回结果。那一刻他明显有点慌而我心里清楚这道被无数人称为“入门第一题”的算法题其实是一把非常精准的尺子量出来的不只是你会不会写循环更是你对时间复杂度的直觉、对查找类问题的理解深度以及在工程里遇到相似场景时能不能快速迁移思路。后来我陆续在好几个项目里遇到和“两数之和”本质相同的需求比如凑单匹配、日志配对、异常组合检测。每一次我都能从这道最朴素的题里找到切入点。所以我特别想把这道题掰开了聊一聊它有多少种解法每种解法背后是什么思维模型面试官到底在考察什么以及作为工程师我们怎么把它真正用起来。这篇文章适合正在准备算法面试的人也适合那些在工作中遇到“从一个集合里找两个元素满足某个关系”但不知道从何下手的开发者。1. 一道小学算术题怎么就成了技术圈的分水岭1.1 题目本身只有一行坑却不止一个题目描述非常短给定一个整数数组nums和一个整数目标值target请你在数组中找出和为目标值的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案但是数组中同一个元素在答案里不能重复出现。按任意顺序返回答案。就这么几句话看起来确实是小学一年级都能看懂的加法。但真动起手来里面的细节比很多人想象的多。首先是“同一个元素不能重复出现”这一条如果数组是[3, 3]target是6答案应该是[0, 1]而直接写两个嵌套循环时很容易出现i j的情况同一个下标被用了两次把nums[0] nums[0]也算成了合法组合这就不对了。其次是负数整数数组里包含负数很常见target也可能是负数如果脑子里只有“两个正数相加”的图像容易漏掉负数的情况。再次是“返回下标”而不是“返回值”这直接决定了某些解法能不能用比如排序完之后下标就乱了得额外存原索引。这些坑单独拎出来都不难但叠加在一起就会筛掉一批“只会写循环”的人。1.2 我在代码评审里见过的最常见翻车现场我做过不少次内部代码评审也看过很多候选人提交的版本。除了双重循环之外最常见的翻车写法有几种使用数组自带的indexOf去查另一半然后在indexOf的结果里用lastIndexOf处理重复值看到底是哪个下标。这种写法逻辑上绕来绕去性能上本质还是O(n²)因为indexOf本身就是一次线性扫描。先把数组排序然后用双指针找两个数最后再用indexOf去查原下标。遇到重复元素时查到的下标永远是最前面那个很容易返回错误结果如果nums里有相同元素比如[2, 2, 7]找9时排序后双指针找到了2和7但indexOf(2)返回0这个结果可能凑巧是对的但一旦两个相同的数分别在数组两端就会出问题。用哈希表只存“已经见过的值”但没处理“当前元素本身就是答案的一部分”的情况。比如查target - nums[i]时如果target - nums[i]恰好等于nums[i]而当前这个值还没有放进哈希表就会出现“找不到”的错误反过来如果先存进去再查又会出现“自己和自己匹配”的问题。这些翻车案例说明一个问题很多人不是不会写代码而是对这道题背后的“查找语义”理解得太浅。哈希表存的是什么、查询的时机是什么、重复值怎么处理这些细节才是题目真正的考点。2. 解法演进从 O(n²) 到 O(n) 的思维跳跃2.1 暴力法最直观也最容易在数据量前暴露问题先看最基础的写法Python 版def two_sum(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开始这一下就规避了i j的问题。代码本身没有错但时间复杂度是O(n²)外层循环跑n次内层循环平均跑n/2次总操作次数大约是n²/2。当n 100时10000次比较对 CPU 来说就是一瞬间当n 100000时5,000,000,000次比较就没那么轻松了。我在面试候选人的时候也见过有人反问“机器不是很快吗”确实快但我们要考虑的是真实业务请求量不是单次离线计算。如果这个函数被线上接口每秒调用几百次每次处理一万条数据O(n²)很快就顶不住了。空间复杂度是O(1)因为只用了常数额外变量。暴力法的价值在于它是一把标尺后面对每个优化都可以拿它当基准对比让复杂度分析变得更具体。2.2 哈希表的两次遍历用空间换时间的第一步既然问题本质是“查找某个数在不在数组里”那我们就该想想怎么让“查找”这个过程比线性扫描更快。绝大多数情况下答案都是哈希表。哈希表可以把“查找某个数是否存在”的平均时间复杂度降到O(1)。于是第一次优化出现了def two_sum(nums, target): value_to_index {} for idx, value in enumerate(nums): value_to_index[value] idx for idx, value in enumerate(nums): complement target - value if complement in value_to_index and value_to_index[complement] ! idx: return [idx, value_to_index[complement]] return []第一遍遍历把所有元素的值和下标塞进哈希表。因为题目说每种输入只会对应一个答案所以当数组里有两个相同元素时后一个会把前一个的下标覆盖掉。这有没有问题在“唯一答案”的前提下没有。比如nums [3, 2, 4]target 6哈希表里3 - 02 - 14 - 2。第二次遍历到2时查到complement 4索引为2不等于当前索引1返回[1, 2]正确。再比如nums [3, 3]target 6哈希表最终为3 - 1因为第二个 3 覆盖了第一个的位置。第二次遍历到idx 0时complement 3查到的索引是1不等于0返回[0, 1]也正确。所以覆盖逻辑在这种约束下是安全的。时间复杂度变成O(n)空间复杂度变成O(n)。这一步的思维跨越是从“每来一个数我就把整个数组再扫一遍”到“我先建一个目录之后每次查目录就行”。想想图书馆查书暴力法相当于每找一个书就沿着书架从头走到尾哈希表法相当于先看一个索引牌直接定位到楼层和区域代价是建索引牌需要额外空间。2.3 一次遍历的增量式哈希更漂亮的写法两次遍历虽然已经是O(n)但仔细想想我们真的需要先完整建好哈希表再查吗其实可以边查边建。当我们遍历到第i个元素时哈希表里只存着下标0到i-1的元素所以即使complement nums[i]哈希表里也不可能有当前这个元素自己。这天然解决了“自己和自己匹配”的问题def two_sum(nums, target): value_to_index {} for idx, value in enumerate(nums): complement target - value if complement in value_to_index: return [value_to_index[complement], idx] value_to_index[value] idx return []比如nums [2, 5, 3]target 4。遍历到idx0时complement 2哈希表为空于是把2 - 0存进去。遍历到idx1时complement -1不在表里把5 - 1存进去。遍历到idx2时complement 1也不在表里最后返回空。注意这里complement出现了负数完全合理。回头看假如用两次遍历遇到nums [2, 2]、target 4的场景一次遍历时idx0查complement 2不在表里因为此时 2 还没放进去然后放进去2-0idx1再查complement 2表里有0返回[0, 1]正确。这种“先查再存”的顺序是整个解法里最精髓的一点它让代码又短又安全。从工程角度看一次遍历还带来一个额外好处对于无限数据流式的输入比如从消息队列里逐条消费数据我们不需要等全量数据到齐才能开始匹配来一条处理一条延迟更低。2.4 排序加双指针一条值得对比却容易踩坑的路线还有一条常见路线是“排序 双指针”。假设数组已经升序排列那我们可以维护左指针和右指针计算nums[left] nums[right]如果和大于target说明大数太大右指针往左移如果和小于target说明小数太小左指针往右移如果相等直接得到结果。def two_sum(nums, target): sorted_nums sorted(nums) left, right 0, len(sorted_nums) - 1 while left right: current_sum sorted_nums[left] sorted_nums[right] if current_sum target: break elif current_sum target: left 1 else: right - 1 # 到这里找到的是数值还需要映射回原数组下标 ...问题来了题目要返回原数组下标。一旦排序下标就全乱了。如果在排序前额外记录原始下标就得自己实现带索引的排序或者用一个二维结构存“值 原下标”。这样总时间复杂度变成O(n log n)因为排序本身就是O(n log n)后面双指针扫描是O(n)加起来是O(n log n)。空间复杂度取决于排序实现通常是O(n)。对比一下三种思路我用一张表总结解法时间复杂度空间复杂度是否保留原下标适用场景暴力双重循环O(n²)O(1)天然保留数据量极小或仅用于验证哈希表两次遍历O(n)O(n)天然保留通用场景数据量大返回索引哈希表一次遍历O(n)O(n)天然保留通用场景推荐首选排序 双指针O(n log n)O(n)需要额外处理输入有序或只需要返回数值在实际做题时我几乎只会选“一次遍历哈希表”但在讨论环节理解排序 双指针同样重要因为它在“返回元素值而非下标”的变体里非常优雅而且“双指针收缩”这种思路是后续三数之和、四数之和等题目的基础。你要不是亲自动手实现一遍很难体会到这里面“排序带来的索引丢失”到底有多容易让人翻车。3. 从算法题到生产环境两数之和的五个现实面孔很多人刷算法题的时候会有一个疑问“这些东西除了面试到底有什么用”我承认不是每道题都能直接映射到业务但“两数之和”是个例外。它的内核是“从集合中找出两个元素使它们的某种关系满足一个给定目标值”。这个描述几乎无处不在。3.1 凑单场景一张订单表里的哈希求助我做过一个电商活动系统的需求用户有几张可用优惠券面额各不相同系统需要判断用户是否能通过“两张券叠加”的方式凑到满减门槛。举个例子满300减50用户手里有[100, 120, 180, 220]如果能找到两张券加起来刚好等于300就在下单页自动推荐“最佳凑单组合”。这个需求翻译一下就是标准的“两数之和”只不过返回的是券面额不是下标。我当时的第一反应就是用一次遍历哈希表把面额放进去来一张查一张。后来数据量大了一张用户券包里可能有几千张券优惠券系统经常有各种渠道发放哈希表依然能轻松应对。注意一个业务细节如果用户有两张相同面额的券比如[150, 150]哈希表存索引时会被第二个覆盖但因为我们要的是“数值”不要求返回是哪一张券的 ID所以只要判断找到了就行。如果要返回券 ID就需要在哈希表里存一个索引列表而不是单个索引。class CouponMatcher: def find_pair(self, coupons, threshold): seen {} for index, amount in enumerate(coupons): diff threshold - amount if diff in seen: return [seen[diff], index] seen[amount] index return None这里的seen就是“已经扫过的券面额”本质和算法题没有区别。但工程上我会多考虑一步如果券数量特别大哈希表的内存占用是否可接受通常一个用户几千张券哈希表几毫秒就建完了完全不是问题。3.2 日志配对时间戳之外的“目标值”思维另一个我实际碰到的场景是日志配对。当时系统里有一个数据同步任务会记录每个批次开始和完成时的日志时间戳。我们需要检查有没有两个批次的时间戳相加后刚好等于某个人为设定的“危险窗口阈值”。这么说有点抽象换个更容易理解的例子假设你维护了一个数据库慢查询日志每条日志里有一个“耗时”字段。DBA 怀疑有“成对出现”的慢查询两个独立查询的耗时叠加或者两个查询的耗时之差等于某个固定值会导致连接池被打满。这时候你从日志里拉出一段时间内的所有查询耗时想要找到“两个耗时相加等于某个目标值”的异常组合。这个问题的难点在于日志量可能非常大上百万条都很正常。暴力双重循环要跑几百亿次显然不现实。用哈希表法把每条耗时存起来再来一条查一条几秒钟就能得到结果。另外“差等于某个固定值”也类似要找a - b k等价于找a和b k。这个“移项”的思想在很多搜索类问题里都通用。两数之和教给我们的不是那几行代码而是“遇到查找关系先想想能不能转化成一个可哈希的键”。3.3 风控中的金额组合检测在支付和风控领域“两数之和”也经常以变体出现。比如风控策略审查资金流水时会关注是否存在两笔交易金额相加后正好等于某个敏感阈值或者是两笔转账的金额之和等于某一笔历史交易的金额。这种异常模式很难用规则直接命中但用哈希表把交易金额索引起来然后逐笔检查“目标金额减去当前金额”是否已经在索引里就能快速筛选出可疑组合。当然真实风控系统比这复杂得多有洗钱路径、多层转账、时序窗口等但最底层的第一步拆分往往就是这种“两两组合匹配”的检测。如果基础算法都不扎实往上叠加图论、时间窗分析会非常吃力。3.4 数据流场景一次遍历哈希表的天然优势前面提到一次遍历哈希表非常适合数据流这在真实工程里非常常见。比如实时日志平台中每来一条日志就判断这条日志和之前的某条日志是否有“互补关系”。如果采用先建完整索引再查询的方式每次来一批新数据都要重建索引代价太高。如果采用边查边存的增量式哈希系统只需要维护一个持续更新的约定数据结构内存占用也能得到控制。这种“在线算法”的思维方式就是两数之和最优解给我们的礼物。我还遇到过一条业务用户上传文件时系统需要判断当前文件和之前上传的某个文件大小相加是否超过限额。文件大小本身是整数哈希表天然可以用。只要把“已上传文件大小”存起来来一个新文件就算一下复杂度很低效果却很好。3.5 把两数之和抽象成“两两关系匹配”的统一模式说到底“两数之和”可以抽象成这样一张图你有一个集合S你对每个元素x计算一个“补数”f(x, target)你判断f(x, target)是否已经被看到过如果看到过就输出这两个元素这里的f不一定非得是target - x它可以是乘法target / x注意除零可以是“两数之差”x - target或者x target甚至可以是更复杂的复合关系比如两数异或等于 target。只要能转化成可哈希的键都能套进这个模式。这就是为什么我特别建议把两数之和吃透的原因它的价值不止于一道题而是一整套“查找配对问题”的解题范式。4. 面试官视角两数之和到底在考什么4.1 候选人最容易忽略的追问如果数组里有重复元素怎么办我在面试中问这道题时喜欢在候选人写完一次遍历哈希表后追加一个问题“如果数组里允许重复元素你的代码还有效吗”很多人会愣一下然后重新审视代码。有效的前提是题目保证“只有一种答案且每个元素只能用一次”。如果有多个重复元素比如nums [2, 2, 3, 3, 4]target 6答案其实有多对2 4的两个 2 都能配3 3也行。但题目只要求返回任意一对所以候选人写的代码依然能返回一对只是无法枚举全部组合。如果面试官继续追问“怎么返回所有组合”那就需要把哈希表的值从“单个索引”改成“索引列表”遍历时依次弹出。这里想考察的并不是记不记得这个细节而是候选人有没有主动考虑“约束条件”。有些人会直接说“题目已经假设唯一答案所以重复没有影响”这是对的有些人会掉进“重复值覆盖索引”的紧张情绪里半天说不清楚这说明他对哈希表操作还没有形成肌肉记忆。我会更欣赏第一种因为它说明候选人是在“解题”而不是在“背答案”。4.2 复杂度计算不是背公式n 的规模决定你的命运以前我帮一个同事排查接口超时最后发现罪魁祸首就是一段双重循环内外两层都是遍历订单列表总数大约八万条。八万的平方是六十四亿即使在最好的情况下一秒钟能跑一亿次简单比较也需要六十多秒。这个例子完美说明了为什么不能只会暴力解法。我在面试时会问“你的解法在什么数据量下会开始变慢如果n是 1000、10000、100000分别需要多少基本操作”候选人如果能快速估算出n²/2的量级说明他对复杂度不是停留在背公式的层面。我用一个生活化类比解释暴力法相当于你每次找一个朋友都要在整座城市里挨家挨户敲门哈希表法是先把每个人的地址记在本子上之后按名字查地址。当人少时敲门法可能还行当城市有十万人时本子法几乎是唯一可行的方案。这个类比我觉得比直接报时间复杂度更能帮助新人建立直觉。4.3 和面试官讨论“排序”时的陷阱面试中有些候选人会主动提到“也可以用排序 双指针”这很好因为说明知识面更广。但紧接着我就问“如果题目要求返回原数组的下标你怎么处理排序导致的索引丢失”很多候选人这时会卡住或者脱口而出“先排序然后用 indexOf 找原下标”但在重复元素存在时indexOf会找到第一个匹配项而这可能不是和当前值配对的那一个。正确的处理方式是提前记录索引用类似(value, index)的结构排序或者创建一个映射数组。这个问题的价值在于考察候选人的“约束敏感度”。一个只背了题解的人可能根本意识不到排序是对数据本身的操作而“下标”是数据的元信息。真正理解问题的人会在一开始就说“因为要返回下标所以哈希表更直接排序会让索引关系丢失除非我们愿意多花内存维护映射关系”。能够主动说出这句话的人在我这里通常能拿到不错的加分。4.4 我总结的一个讲题框架从暴力到最优每一步都要给出理由面试里这道题的标准讲法我建议按下面这个框架来这也是我自己准备别人时用的思路先复述题目和面试官确认是否只有唯一答案数组可能为空吗元素可以是负数吗返回下标还是值从暴力法开始不要跳步。清楚地写出双重循环并主动说出时间复杂度是 O(n²)、空间复杂度是 O(1)。分析瓶颈每次查找另一个数都需要线性扫描我们想加速“查找”。引出哈希表把已经见过的值存起来让查找变成 O(1)。先写“两次遍历”版本再说“一次遍历”优化。再次总结复杂度O(n) 时间、O(n) 空间。主动讨论边界情况重复元素、空数组、负数、自己不能匹配自己。如果时间有余再提一句排序 双指针方案以及它的局限性。这个框架的好处是它有“生长感”像在逐步推演一个想法而不是直接把最优解拍在桌子上。面试官听到这种思路通常会觉得这个候选人不是死记硬背而是真的理解了算法的演进逻辑。我自己面试别人时也会更愿意给“能讲清楚为什么”的人通过因为实际项目里你要经常给同事解释你的设计方案阐述“为什么”是一种核心工程能力。5. 举一反三从两数之和出发的算法谱系5.1 两数之和 II输入有序时的新解法LeetCode 上有另一道题叫“两数之和 II - 输入有序数组”唯一的区别是输入的数组已经按升序排列。这时候“排序 双指针”就非常自然因为不需要担心排序会丢索引直接一个左指针和右指针收缩就行。def two_sum_sorted(numbers, target): left, right 0, len(numbers) - 1 while left right: total numbers[left] numbers[right] if total target: return [left 1, right 1] # 题目要求下标从 1 开始 elif total target: left 1 else: right - 1 return []看到这个解法再回想无序版本的“排序 双指针”你会明白核心思想的适应条件双指针法依赖“有序”而哈希表法不依赖。有序时双指针空间复杂度 O(1)这是它比哈希表更优的地方。所以你看同一个问题输入条件一变最优解就可能完全不同。5.2 三数之和把两数之和套在循环里“三数之和”也是经典题从数组中找出三个数使它们的和等于 0。最简单的思路是三重循环但那是 O(n³)。优化思路是先排序然后逐个固定第一个数剩下两个数用“双指针”在有序数组里找。def three_sum(nums): nums.sort() result [] n len(nums) for i in range(n - 2): 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: result.append([nums[i], nums[left], nums[right]]) left 1 right - 1 while left right and nums[left] nums[left - 1]: left 1 while left right and nums[right] nums[right 1]: right - 1 elif total 0: left 1 else: right - 1 return result这里去重逻辑是重点如果忽略它会出现重复三元组。你会发现外层循环无非是在遍历“第一个数”内层就是“有序数组的两数之和双指针版”。这就是两数之和思想最直接的复用。5.3 给不同阶段学习者的实操建议对于刚开始接触算法的人我的建议是不要急着把题目从 1 刷到 2000。先把“两数之和”这一系列吃透理解复杂度从 O(n²) 到 O(n) 的思维跳跃然后尝试变体两数之和 II、三数之和、四数之和、两数之差、两数之积。每做一道变体都问自己三个问题这个变体改变了什么约束有序返回下标返回所有组合原有的哈希表法还能用吗双指针法呢如果数据量变成一百倍我的解法会崩吗这种“举一反三”的练习方式比机械刷题有效得多。我自己带过的实习生凡是用这个节奏学习的基本两三周内就能建立起对“查找类问题”的直觉后续遇到商业系统的配对场景也能很快想到该用什么数据结构。如果你已经在工作中我的额外建议是尝试在一周内找到自己业务代码里至少一个“两两配对”的潜在线索然后试着用哈希表去重写一遍。哪怕只是内部工具脚本也能帮你对这个算法产生肌肉记忆。技术成长从来不是靠背题而是靠把题里的思维模型搬进真实场景。这道题目、这段代码、这张哈希表最终会成为你工具箱里那把最常用的螺丝刀。
两数之和算法全解：从暴力破解到哈希表与双指针优化
第一次遇到“两数之和”是在一场技术面试的现场不过我不是面试者而是坐在对面听候选人讲思路的面试官。当时候选人用了不到五分钟写了一个双重循环然后抬头说“做完了”。我让他打开终端自己生成一个长度为十万的随机数组然后跑一下那段代码。他连续敲了几次回车程序都没在预期时间内返回结果。那一刻他明显有点慌而我心里清楚这道被无数人称为“入门第一题”的算法题其实是一把非常精准的尺子量出来的不只是你会不会写循环更是你对时间复杂度的直觉、对查找类问题的理解深度以及在工程里遇到相似场景时能不能快速迁移思路。后来我陆续在好几个项目里遇到和“两数之和”本质相同的需求比如凑单匹配、日志配对、异常组合检测。每一次我都能从这道最朴素的题里找到切入点。所以我特别想把这道题掰开了聊一聊它有多少种解法每种解法背后是什么思维模型面试官到底在考察什么以及作为工程师我们怎么把它真正用起来。这篇文章适合正在准备算法面试的人也适合那些在工作中遇到“从一个集合里找两个元素满足某个关系”但不知道从何下手的开发者。1. 一道小学算术题怎么就成了技术圈的分水岭1.1 题目本身只有一行坑却不止一个题目描述非常短给定一个整数数组nums和一个整数目标值target请你在数组中找出和为目标值的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案但是数组中同一个元素在答案里不能重复出现。按任意顺序返回答案。就这么几句话看起来确实是小学一年级都能看懂的加法。但真动起手来里面的细节比很多人想象的多。首先是“同一个元素不能重复出现”这一条如果数组是[3, 3]target是6答案应该是[0, 1]而直接写两个嵌套循环时很容易出现i j的情况同一个下标被用了两次把nums[0] nums[0]也算成了合法组合这就不对了。其次是负数整数数组里包含负数很常见target也可能是负数如果脑子里只有“两个正数相加”的图像容易漏掉负数的情况。再次是“返回下标”而不是“返回值”这直接决定了某些解法能不能用比如排序完之后下标就乱了得额外存原索引。这些坑单独拎出来都不难但叠加在一起就会筛掉一批“只会写循环”的人。1.2 我在代码评审里见过的最常见翻车现场我做过不少次内部代码评审也看过很多候选人提交的版本。除了双重循环之外最常见的翻车写法有几种使用数组自带的indexOf去查另一半然后在indexOf的结果里用lastIndexOf处理重复值看到底是哪个下标。这种写法逻辑上绕来绕去性能上本质还是O(n²)因为indexOf本身就是一次线性扫描。先把数组排序然后用双指针找两个数最后再用indexOf去查原下标。遇到重复元素时查到的下标永远是最前面那个很容易返回错误结果如果nums里有相同元素比如[2, 2, 7]找9时排序后双指针找到了2和7但indexOf(2)返回0这个结果可能凑巧是对的但一旦两个相同的数分别在数组两端就会出问题。用哈希表只存“已经见过的值”但没处理“当前元素本身就是答案的一部分”的情况。比如查target - nums[i]时如果target - nums[i]恰好等于nums[i]而当前这个值还没有放进哈希表就会出现“找不到”的错误反过来如果先存进去再查又会出现“自己和自己匹配”的问题。这些翻车案例说明一个问题很多人不是不会写代码而是对这道题背后的“查找语义”理解得太浅。哈希表存的是什么、查询的时机是什么、重复值怎么处理这些细节才是题目真正的考点。2. 解法演进从 O(n²) 到 O(n) 的思维跳跃2.1 暴力法最直观也最容易在数据量前暴露问题先看最基础的写法Python 版def two_sum(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开始这一下就规避了i j的问题。代码本身没有错但时间复杂度是O(n²)外层循环跑n次内层循环平均跑n/2次总操作次数大约是n²/2。当n 100时10000次比较对 CPU 来说就是一瞬间当n 100000时5,000,000,000次比较就没那么轻松了。我在面试候选人的时候也见过有人反问“机器不是很快吗”确实快但我们要考虑的是真实业务请求量不是单次离线计算。如果这个函数被线上接口每秒调用几百次每次处理一万条数据O(n²)很快就顶不住了。空间复杂度是O(1)因为只用了常数额外变量。暴力法的价值在于它是一把标尺后面对每个优化都可以拿它当基准对比让复杂度分析变得更具体。2.2 哈希表的两次遍历用空间换时间的第一步既然问题本质是“查找某个数在不在数组里”那我们就该想想怎么让“查找”这个过程比线性扫描更快。绝大多数情况下答案都是哈希表。哈希表可以把“查找某个数是否存在”的平均时间复杂度降到O(1)。于是第一次优化出现了def two_sum(nums, target): value_to_index {} for idx, value in enumerate(nums): value_to_index[value] idx for idx, value in enumerate(nums): complement target - value if complement in value_to_index and value_to_index[complement] ! idx: return [idx, value_to_index[complement]] return []第一遍遍历把所有元素的值和下标塞进哈希表。因为题目说每种输入只会对应一个答案所以当数组里有两个相同元素时后一个会把前一个的下标覆盖掉。这有没有问题在“唯一答案”的前提下没有。比如nums [3, 2, 4]target 6哈希表里3 - 02 - 14 - 2。第二次遍历到2时查到complement 4索引为2不等于当前索引1返回[1, 2]正确。再比如nums [3, 3]target 6哈希表最终为3 - 1因为第二个 3 覆盖了第一个的位置。第二次遍历到idx 0时complement 3查到的索引是1不等于0返回[0, 1]也正确。所以覆盖逻辑在这种约束下是安全的。时间复杂度变成O(n)空间复杂度变成O(n)。这一步的思维跨越是从“每来一个数我就把整个数组再扫一遍”到“我先建一个目录之后每次查目录就行”。想想图书馆查书暴力法相当于每找一个书就沿着书架从头走到尾哈希表法相当于先看一个索引牌直接定位到楼层和区域代价是建索引牌需要额外空间。2.3 一次遍历的增量式哈希更漂亮的写法两次遍历虽然已经是O(n)但仔细想想我们真的需要先完整建好哈希表再查吗其实可以边查边建。当我们遍历到第i个元素时哈希表里只存着下标0到i-1的元素所以即使complement nums[i]哈希表里也不可能有当前这个元素自己。这天然解决了“自己和自己匹配”的问题def two_sum(nums, target): value_to_index {} for idx, value in enumerate(nums): complement target - value if complement in value_to_index: return [value_to_index[complement], idx] value_to_index[value] idx return []比如nums [2, 5, 3]target 4。遍历到idx0时complement 2哈希表为空于是把2 - 0存进去。遍历到idx1时complement -1不在表里把5 - 1存进去。遍历到idx2时complement 1也不在表里最后返回空。注意这里complement出现了负数完全合理。回头看假如用两次遍历遇到nums [2, 2]、target 4的场景一次遍历时idx0查complement 2不在表里因为此时 2 还没放进去然后放进去2-0idx1再查complement 2表里有0返回[0, 1]正确。这种“先查再存”的顺序是整个解法里最精髓的一点它让代码又短又安全。从工程角度看一次遍历还带来一个额外好处对于无限数据流式的输入比如从消息队列里逐条消费数据我们不需要等全量数据到齐才能开始匹配来一条处理一条延迟更低。2.4 排序加双指针一条值得对比却容易踩坑的路线还有一条常见路线是“排序 双指针”。假设数组已经升序排列那我们可以维护左指针和右指针计算nums[left] nums[right]如果和大于target说明大数太大右指针往左移如果和小于target说明小数太小左指针往右移如果相等直接得到结果。def two_sum(nums, target): sorted_nums sorted(nums) left, right 0, len(sorted_nums) - 1 while left right: current_sum sorted_nums[left] sorted_nums[right] if current_sum target: break elif current_sum target: left 1 else: right - 1 # 到这里找到的是数值还需要映射回原数组下标 ...问题来了题目要返回原数组下标。一旦排序下标就全乱了。如果在排序前额外记录原始下标就得自己实现带索引的排序或者用一个二维结构存“值 原下标”。这样总时间复杂度变成O(n log n)因为排序本身就是O(n log n)后面双指针扫描是O(n)加起来是O(n log n)。空间复杂度取决于排序实现通常是O(n)。对比一下三种思路我用一张表总结解法时间复杂度空间复杂度是否保留原下标适用场景暴力双重循环O(n²)O(1)天然保留数据量极小或仅用于验证哈希表两次遍历O(n)O(n)天然保留通用场景数据量大返回索引哈希表一次遍历O(n)O(n)天然保留通用场景推荐首选排序 双指针O(n log n)O(n)需要额外处理输入有序或只需要返回数值在实际做题时我几乎只会选“一次遍历哈希表”但在讨论环节理解排序 双指针同样重要因为它在“返回元素值而非下标”的变体里非常优雅而且“双指针收缩”这种思路是后续三数之和、四数之和等题目的基础。你要不是亲自动手实现一遍很难体会到这里面“排序带来的索引丢失”到底有多容易让人翻车。3. 从算法题到生产环境两数之和的五个现实面孔很多人刷算法题的时候会有一个疑问“这些东西除了面试到底有什么用”我承认不是每道题都能直接映射到业务但“两数之和”是个例外。它的内核是“从集合中找出两个元素使它们的某种关系满足一个给定目标值”。这个描述几乎无处不在。3.1 凑单场景一张订单表里的哈希求助我做过一个电商活动系统的需求用户有几张可用优惠券面额各不相同系统需要判断用户是否能通过“两张券叠加”的方式凑到满减门槛。举个例子满300减50用户手里有[100, 120, 180, 220]如果能找到两张券加起来刚好等于300就在下单页自动推荐“最佳凑单组合”。这个需求翻译一下就是标准的“两数之和”只不过返回的是券面额不是下标。我当时的第一反应就是用一次遍历哈希表把面额放进去来一张查一张。后来数据量大了一张用户券包里可能有几千张券优惠券系统经常有各种渠道发放哈希表依然能轻松应对。注意一个业务细节如果用户有两张相同面额的券比如[150, 150]哈希表存索引时会被第二个覆盖但因为我们要的是“数值”不要求返回是哪一张券的 ID所以只要判断找到了就行。如果要返回券 ID就需要在哈希表里存一个索引列表而不是单个索引。class CouponMatcher: def find_pair(self, coupons, threshold): seen {} for index, amount in enumerate(coupons): diff threshold - amount if diff in seen: return [seen[diff], index] seen[amount] index return None这里的seen就是“已经扫过的券面额”本质和算法题没有区别。但工程上我会多考虑一步如果券数量特别大哈希表的内存占用是否可接受通常一个用户几千张券哈希表几毫秒就建完了完全不是问题。3.2 日志配对时间戳之外的“目标值”思维另一个我实际碰到的场景是日志配对。当时系统里有一个数据同步任务会记录每个批次开始和完成时的日志时间戳。我们需要检查有没有两个批次的时间戳相加后刚好等于某个人为设定的“危险窗口阈值”。这么说有点抽象换个更容易理解的例子假设你维护了一个数据库慢查询日志每条日志里有一个“耗时”字段。DBA 怀疑有“成对出现”的慢查询两个独立查询的耗时叠加或者两个查询的耗时之差等于某个固定值会导致连接池被打满。这时候你从日志里拉出一段时间内的所有查询耗时想要找到“两个耗时相加等于某个目标值”的异常组合。这个问题的难点在于日志量可能非常大上百万条都很正常。暴力双重循环要跑几百亿次显然不现实。用哈希表法把每条耗时存起来再来一条查一条几秒钟就能得到结果。另外“差等于某个固定值”也类似要找a - b k等价于找a和b k。这个“移项”的思想在很多搜索类问题里都通用。两数之和教给我们的不是那几行代码而是“遇到查找关系先想想能不能转化成一个可哈希的键”。3.3 风控中的金额组合检测在支付和风控领域“两数之和”也经常以变体出现。比如风控策略审查资金流水时会关注是否存在两笔交易金额相加后正好等于某个敏感阈值或者是两笔转账的金额之和等于某一笔历史交易的金额。这种异常模式很难用规则直接命中但用哈希表把交易金额索引起来然后逐笔检查“目标金额减去当前金额”是否已经在索引里就能快速筛选出可疑组合。当然真实风控系统比这复杂得多有洗钱路径、多层转账、时序窗口等但最底层的第一步拆分往往就是这种“两两组合匹配”的检测。如果基础算法都不扎实往上叠加图论、时间窗分析会非常吃力。3.4 数据流场景一次遍历哈希表的天然优势前面提到一次遍历哈希表非常适合数据流这在真实工程里非常常见。比如实时日志平台中每来一条日志就判断这条日志和之前的某条日志是否有“互补关系”。如果采用先建完整索引再查询的方式每次来一批新数据都要重建索引代价太高。如果采用边查边存的增量式哈希系统只需要维护一个持续更新的约定数据结构内存占用也能得到控制。这种“在线算法”的思维方式就是两数之和最优解给我们的礼物。我还遇到过一条业务用户上传文件时系统需要判断当前文件和之前上传的某个文件大小相加是否超过限额。文件大小本身是整数哈希表天然可以用。只要把“已上传文件大小”存起来来一个新文件就算一下复杂度很低效果却很好。3.5 把两数之和抽象成“两两关系匹配”的统一模式说到底“两数之和”可以抽象成这样一张图你有一个集合S你对每个元素x计算一个“补数”f(x, target)你判断f(x, target)是否已经被看到过如果看到过就输出这两个元素这里的f不一定非得是target - x它可以是乘法target / x注意除零可以是“两数之差”x - target或者x target甚至可以是更复杂的复合关系比如两数异或等于 target。只要能转化成可哈希的键都能套进这个模式。这就是为什么我特别建议把两数之和吃透的原因它的价值不止于一道题而是一整套“查找配对问题”的解题范式。4. 面试官视角两数之和到底在考什么4.1 候选人最容易忽略的追问如果数组里有重复元素怎么办我在面试中问这道题时喜欢在候选人写完一次遍历哈希表后追加一个问题“如果数组里允许重复元素你的代码还有效吗”很多人会愣一下然后重新审视代码。有效的前提是题目保证“只有一种答案且每个元素只能用一次”。如果有多个重复元素比如nums [2, 2, 3, 3, 4]target 6答案其实有多对2 4的两个 2 都能配3 3也行。但题目只要求返回任意一对所以候选人写的代码依然能返回一对只是无法枚举全部组合。如果面试官继续追问“怎么返回所有组合”那就需要把哈希表的值从“单个索引”改成“索引列表”遍历时依次弹出。这里想考察的并不是记不记得这个细节而是候选人有没有主动考虑“约束条件”。有些人会直接说“题目已经假设唯一答案所以重复没有影响”这是对的有些人会掉进“重复值覆盖索引”的紧张情绪里半天说不清楚这说明他对哈希表操作还没有形成肌肉记忆。我会更欣赏第一种因为它说明候选人是在“解题”而不是在“背答案”。4.2 复杂度计算不是背公式n 的规模决定你的命运以前我帮一个同事排查接口超时最后发现罪魁祸首就是一段双重循环内外两层都是遍历订单列表总数大约八万条。八万的平方是六十四亿即使在最好的情况下一秒钟能跑一亿次简单比较也需要六十多秒。这个例子完美说明了为什么不能只会暴力解法。我在面试时会问“你的解法在什么数据量下会开始变慢如果n是 1000、10000、100000分别需要多少基本操作”候选人如果能快速估算出n²/2的量级说明他对复杂度不是停留在背公式的层面。我用一个生活化类比解释暴力法相当于你每次找一个朋友都要在整座城市里挨家挨户敲门哈希表法是先把每个人的地址记在本子上之后按名字查地址。当人少时敲门法可能还行当城市有十万人时本子法几乎是唯一可行的方案。这个类比我觉得比直接报时间复杂度更能帮助新人建立直觉。4.3 和面试官讨论“排序”时的陷阱面试中有些候选人会主动提到“也可以用排序 双指针”这很好因为说明知识面更广。但紧接着我就问“如果题目要求返回原数组的下标你怎么处理排序导致的索引丢失”很多候选人这时会卡住或者脱口而出“先排序然后用 indexOf 找原下标”但在重复元素存在时indexOf会找到第一个匹配项而这可能不是和当前值配对的那一个。正确的处理方式是提前记录索引用类似(value, index)的结构排序或者创建一个映射数组。这个问题的价值在于考察候选人的“约束敏感度”。一个只背了题解的人可能根本意识不到排序是对数据本身的操作而“下标”是数据的元信息。真正理解问题的人会在一开始就说“因为要返回下标所以哈希表更直接排序会让索引关系丢失除非我们愿意多花内存维护映射关系”。能够主动说出这句话的人在我这里通常能拿到不错的加分。4.4 我总结的一个讲题框架从暴力到最优每一步都要给出理由面试里这道题的标准讲法我建议按下面这个框架来这也是我自己准备别人时用的思路先复述题目和面试官确认是否只有唯一答案数组可能为空吗元素可以是负数吗返回下标还是值从暴力法开始不要跳步。清楚地写出双重循环并主动说出时间复杂度是 O(n²)、空间复杂度是 O(1)。分析瓶颈每次查找另一个数都需要线性扫描我们想加速“查找”。引出哈希表把已经见过的值存起来让查找变成 O(1)。先写“两次遍历”版本再说“一次遍历”优化。再次总结复杂度O(n) 时间、O(n) 空间。主动讨论边界情况重复元素、空数组、负数、自己不能匹配自己。如果时间有余再提一句排序 双指针方案以及它的局限性。这个框架的好处是它有“生长感”像在逐步推演一个想法而不是直接把最优解拍在桌子上。面试官听到这种思路通常会觉得这个候选人不是死记硬背而是真的理解了算法的演进逻辑。我自己面试别人时也会更愿意给“能讲清楚为什么”的人通过因为实际项目里你要经常给同事解释你的设计方案阐述“为什么”是一种核心工程能力。5. 举一反三从两数之和出发的算法谱系5.1 两数之和 II输入有序时的新解法LeetCode 上有另一道题叫“两数之和 II - 输入有序数组”唯一的区别是输入的数组已经按升序排列。这时候“排序 双指针”就非常自然因为不需要担心排序会丢索引直接一个左指针和右指针收缩就行。def two_sum_sorted(numbers, target): left, right 0, len(numbers) - 1 while left right: total numbers[left] numbers[right] if total target: return [left 1, right 1] # 题目要求下标从 1 开始 elif total target: left 1 else: right - 1 return []看到这个解法再回想无序版本的“排序 双指针”你会明白核心思想的适应条件双指针法依赖“有序”而哈希表法不依赖。有序时双指针空间复杂度 O(1)这是它比哈希表更优的地方。所以你看同一个问题输入条件一变最优解就可能完全不同。5.2 三数之和把两数之和套在循环里“三数之和”也是经典题从数组中找出三个数使它们的和等于 0。最简单的思路是三重循环但那是 O(n³)。优化思路是先排序然后逐个固定第一个数剩下两个数用“双指针”在有序数组里找。def three_sum(nums): nums.sort() result [] n len(nums) for i in range(n - 2): 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: result.append([nums[i], nums[left], nums[right]]) left 1 right - 1 while left right and nums[left] nums[left - 1]: left 1 while left right and nums[right] nums[right 1]: right - 1 elif total 0: left 1 else: right - 1 return result这里去重逻辑是重点如果忽略它会出现重复三元组。你会发现外层循环无非是在遍历“第一个数”内层就是“有序数组的两数之和双指针版”。这就是两数之和思想最直接的复用。5.3 给不同阶段学习者的实操建议对于刚开始接触算法的人我的建议是不要急着把题目从 1 刷到 2000。先把“两数之和”这一系列吃透理解复杂度从 O(n²) 到 O(n) 的思维跳跃然后尝试变体两数之和 II、三数之和、四数之和、两数之差、两数之积。每做一道变体都问自己三个问题这个变体改变了什么约束有序返回下标返回所有组合原有的哈希表法还能用吗双指针法呢如果数据量变成一百倍我的解法会崩吗这种“举一反三”的练习方式比机械刷题有效得多。我自己带过的实习生凡是用这个节奏学习的基本两三周内就能建立起对“查找类问题”的直觉后续遇到商业系统的配对场景也能很快想到该用什么数据结构。如果你已经在工作中我的额外建议是尝试在一周内找到自己业务代码里至少一个“两两配对”的潜在线索然后试着用哈希表去重写一遍。哪怕只是内部工具脚本也能帮你对这个算法产生肌肉记忆。技术成长从来不是靠背题而是靠把题里的思维模型搬进真实场景。这道题目、这段代码、这张哈希表最终会成为你工具箱里那把最常用的螺丝刀。
