哈希表入门：两数之和与存在重复元素的同源解法-北京尧图网络

看到系列第一讲把“两数之和”和“存在重复元素”摆在一起我一开始是有点疑惑的。一道是配对查找一道是去重检测一个要返回下标一个只给真假怎么看都像两码事。直到我把两个答案并排写在纸上才发现它们几乎是同一个知识点换了两张皮都是在一遍遍历的过程里用哈希表快速回答“这个数以前见过吗”。两数之和问的是“能跟我凑成 target 的数以前出现过吗”存在重复元素问的是“当前这个数以前出现过吗”。区别只是查询条件不同骨子里完全是同一套逻辑。这篇笔记适合刚起步刷算法题的人也适合想系统梳理哈希表基础的老手。我会把两道题的完整推导过程、边界条件、高频变体和踩过的坑一次讲清楚并提供可以直接拿去用的复盘方法。1. 两数之和与存在重复元素本质上是同一个问题1.1 先把题目卡片摆清楚两数之和在线判题平台第1题给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值target的那两个整数并返回它们的数组下标。题目保证只有一种答案且数组中同一个元素不能使用两遍。存在重复元素在线判题平台第217题给你一个整数数组nums如果任一值在数组中出现至少两次返回true如果数组中每个元素互不相同返回false。两张卡片放在一起差异很明显一个要下标一个只要布尔值。但如果把两数之和的返回条件改成“是否存在这样一对数”再把存在重复元素的判定条件改成“是否已经见过当前这个数”你会发现它们共用同一套遍历框架。1.2 剥掉外壳之后两题都在做同一件事两道题都需要在遍历过程中“记住已经见过的东西”然后做一次快速查询。数组遍历是个顺序过程哈希表恰好提供了两个基础操作插入一个元素、查询某个元素是否存在两者平均时间复杂度都是 O(1)。两数之和走到第i个位置时我想知道的是target - nums[i]这个数是否在我已经走过的区间里出现过。这是一个查找问题。存在重复元素走到第i个位置时我想知道的是nums[i]是否在我已经走过的区间里出现过。这也是一个查找问题。差别只在查询键一个按“差值”查一个按“当前值”查。理解了这层关系再看后面的代码就会发现两道题的核心逻辑几乎一模一样就是一个“查一下没有就存进去”的循环。1.3 为什么是哈希表而不是数组或平衡树这个问题我带新人的时候经常被问到。数组只有在已知下标时才能做到 O(1)按值去查就得从头遍历复杂度是 O(n)。如果每走一步都要做一次 O(n) 的查找整体就是 O(n²)这正是暴力解法的来源。平衡树也能做插入和查询但两者都是 O(log n)整体 O(n log n)不是不能用而是没必要。哈希表是用空间换时间把“按值查询”的成本摊到了常数级别。在“一边遍历一边积累记忆”的场景里它就是最顺手的那把刀。如果面试官追问“为什么不用红黑树”你要能答出这个 O(1) 和 O(log n) 的差别这道题才算真正过关。2. 两数之和——从双重循环到一遍哈希的完整进化路径2.1 暴力解能跑通但只配用来验证正确性最直接的思路是两重循环枚举所有(i, j)组合。代码很短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 []分析一下就知道问题在哪n 个元素的两两组合一共有 n*(n-1)/2 种时间复杂度 O(n²)。数组长度小的时候无所谓一旦数据量到几千运行时间会肉眼可见地上升。我见过有同学在面试里写完暴力解自信地说“这不就完了吗”面试官往往不会直接否定而是接一句“那你怎么优化”。提前把这层想清楚比被动接招要好得多。这版代码虽然不优秀但我建议保留它。它是正确性的基准后面两种优化版本写完拿随机测试和暴力版对拍可以快速确认新逻辑没有改坏。刷题初期这个习惯能帮你节省大量排查时间。2.2 两遍哈希先登记再找人暴力解慢在“找另一半”需要扫描整个数组。哈希表可以把这个过程缩短到 O(1)。第一遍遍历把每个数字和它的下标存进哈希表第二遍遍历对每个nums[i]查“target - nums[i]是否在表里并且配对下标不是i自己”。def two_sum(nums, target): num_index {} for i, num in enumerate(nums): num_index[num] i for i, num in enumerate(nums): diff target - num if diff in num_index and num_index[diff] ! i: return [i, num_index[diff]] return []注意num_index[diff] ! i这个判断。比如数组[3, 2, 4]、target 6在i 0的位置diff 3而3正好在表里且下标也是0。如果少了这个判断代码会返回[0, 0]等于把同一个元素用了两遍这不符合题目要求。两遍哈希写法里最容易踩的就是这个坑。2.3 一遍哈希边走边记录的精妙之处两遍哈希已经很好但还能再进一步。想想看答案里那一对数字总是“先出现的那一个被存起来后出现的那一个负责把它查出来”。所以我完全可以在遍历的同一轮里先查表再把当前数字放进去。def two_sum(nums, target): seen {} for i, num in enumerate(nums): diff target - num if diff in seen: return [seen[diff], i] seen[num] i return []省了一次遍历代码也更短。更关键的是它天然规避了“同一个元素用两遍”的问题因为当前元素还没放进表里你查到的一定是之前出现过的元素。解法时间复杂度空间复杂度核心思路暴力两重循环O(n²)O(1)枚举所有配对两遍哈希O(n)O(n)先建表再查表一遍哈希O(n)O(n)边查边建表2.4 担心“自己匹配自己”模拟一遍就懂了这是我当年学这道题卡得最久的地方。拿nums [3, 3]、target 6走一遍一遍哈希第一步i 0num 3diff 3此时seen是空的查不到于是把3:0放进去。第二步i 1num 3diff 3此时查到了下标0返回[0, 1]。整个过程中当前元素始终没有参与自己的查询。如果两个相同值的元素构成答案第一个 3 出现时第二个 3 还没来它只能等着等第二个 3 到了第一个 3 已经躺在表里了自然就配上了。所以只要保证“先查询、后插入”这个矛盾就不存在。这个顺序不能颠倒否则你就需要额外的! i判断来兜底。3. 两数之和的边界条件与高频变体比背答案更重要3.1 边界条件清单不测完别说自己会了我给自己定的规矩是写完代码必须跑一遍边界用例最少包含下面这几类[2, 7, 11, 15]target 9期望[0, 1]正常情况。[3, 2, 4]target 6期望[1, 2]。这个用例专门用来卡暴力解的编号顺序。[3, 3]target 6期望[0, 1]。重复数字构成答案。[1, 2, 3]target 7无解。按题目约定返回空。空数组、只有一个元素的数组同样要返回空。第三和第四条尤其重要。很多实现能在“正常用例”上跑通一到重复数字就出错原因往往是“先全量建表再查表”时忘了排除自己而到了无解用例有的同学直接返回None到了在线判题平台就会因为返回类型不一致被卡。做算法题边界条件和功能实现同等份量缺一不可。3.2 为什么排序加双指针在这里不成立这是面试里出现频率极高的一问。如果题目问的不是下标而是“是否存在两个数之和等于 target”那完全可以先排序再用双指针从两端往中间移动空间复杂度能压到 O(1)。但本题要的是下标——排序会把原始位置打乱你再也没办法还原排序前的下标了。有人会说“我可以额外存一份排序前的下标”确实可以但既然最终还要保留位置信息哈希表本来就存了一份下标索引再用排序加双指针就是多此一举。每次动手前先看题目要的是“值”还是“下标”这一个字直接决定算法路线。这个判断训练多了慢慢就有了“看到题目先分类”的条件反射。3.3 面试最爱问的两个变体变体一返回所有不重复的组合而不是一个下标对。哈希表依然能用但要去重。惯用的做法是先排序循环里跳过重复值或者用计数器记录每个数字的出现次数只对“第一次出现”的数字尝试配对。变体二数组有序仍然返回下标。有了顺序性双指针就是最优解O(n) 时间、O(1) 空间比哈希表还省内存。我建议把这个变体的代码也写一遍它能帮你建立“根据条件切换解法”的意识而不是只会背哈希表口诀。4. 存在重复元素——哈希集合还是原地排序4.1 哈希集合最简单的 O(n) 解法这道题不需要记录“这个数出现在哪个下标”只需要知道“它出现过没有”所以用集合就够了。Python 里是setJava 里是HashSet。逻辑只有三步遇到一个数先查集合里有没有没有就放进去有就直接返回true。def contains_duplicate(nums): seen set() for num in nums: if num in seen: return True seen.add(num) return False时间复杂度 O(n)空间复杂度 O(n)。这版代码简单到有点对不起“算法题”三个字但它背后是哈希表最基础的“判重”能力。后面刷第219题、第220题都是在这版代码上做限制条件的扩充。4.2 排序解法把额外空间省下来如果不太能接受 O(n) 的额外空间那就排序。排序之后重复的值一定会相邻排在一起所以只要比较相邻两个元素是否相等即可。def contains_duplicate(nums): nums.sort() for i in range(1, len(nums)): if nums[i] nums[i - 1]: return True return False时间复杂度 O(n log n)空间复杂度 O(1)原地修改数组。刷题的时候很多人默认时间优先直接选哈希集合这本身没有错但我建议把排序解法也写一遍。原因有两个一是很多面试官会追问“内存有限制怎么办”二是数据规模不大或者重复元素靠前时排序解法的常数小实测可能比哈希集合还快。大 O 只是参考常数和实际数据分布也要看。解法时间复杂度空间复杂度适用场景哈希集合O(n)O(n)时间优先内存充足排序比较O(n log n)O(1)空间受限允许修改数组4.3 面试追问内存放不下的时候怎么办哈希集合虽然快但要额外 O(n) 的内存。如果数组规模极大内存装不下完整集合“时间快”就失去意义。常规的应对有两条路第一外部分治。把数组分块读入每一块内部用哈希集合判重块与块之间再处理边界上的重复元素。相当于用“分治加外存”把内存压力摊薄海量数据处理里经常用这个思路。第二如果整数取值范围有限且已知可以用位图。比如值域在 0 到几百万之间几十 MB 的位图就能覆盖整个值域判重变成一个位操作时间和空间都极其优越。这两条路在常规刷题里基本用不上但一旦面试官把话题引向“海量数据”你能接住这个话头区分度立刻就出来了。4.4 从217到219、220难度是怎么逐步升级的这题是题库第217题后面还有两个直系变体。第219题“存在重复元素 II”加了一个条件重复的两个元素下标差不超过k。解法是把裸集合升级成“滑动窗口加哈希集合”窗口内只保留最近k个元素每步先查当前元素是否在窗口内再把窗口滑下去。第220题“存在重复元素 III”更进一步要求下标差不超过k且值差不超过t。这就既要维护一个滑动窗口又要在窗口内快速查询“值附近有没有数”一般用有序集合或分桶来做。看着是一步步变难其实每次加限制条件都是在原来的“判重”骨架上叠加一个额外的数据结构。我在刷题时习惯把这种“骨架加限制”的演进路线直接写进笔记比零散记题号有用得多。5. 这两道题到底在训练什么以及我的刷题建议5.1 可带走的是一个模式不是两道题如果只记住“两数之和用哈希表、存在重复元素用集合”刷题刷到后面会很痛苦。题目是刷不完的模式才是能带走的东西。这两道题放在系列开篇核心训练目标只有一个在一遍遍历的过程中用哈希表维护一个“已经见过的集合”再用 O(1) 的查询回答“当前这个元素配不配对”。后面很多题目都是这个模式的变体字母异位词分组需要把排序后的字符串当作键最长连续序列需要判断“某个数的前一个数是否出现过”连续子数组和为k需要在哈希表里存储前缀和出现的次数。表层完全不同骨架完全一样。先把这套骨架练熟再去看那些题会发现上手速度快很多。5.2 一个通用复盘模板每道题都套一遍我自己的习惯是每道题 AC 之后不急着刷下一条而是按四步写复盘一这题让我查什么查询条件是什么。二暴力解慢在哪一步的重复劳动上。三优化后的解法用哪个数据结构消除了那种重复劳动。四如果题目改一个条件解法会怎么变。拿两数之和套模板题目让我查“target减当前值”是否出现过慢在每次都要全数组扫描哈希表把扫描变成了 O(1) 查询如果题目改成有序数组的下标对就可以用双指针。模板不必固定但一定要有自己的固定动作。这样积累下来的不是题量而是一棵决策树。5.3 给初学者的几条具体建议先亲手写一遍暴力解再写优化解不要直接背最优解。暴力解是理解的起点也是正确性的基准。用纸笔画一遍模拟过程至少把两数之和按照三五个用例完整走一遍不跳步再动手写代码。代码写完把边界条件清单过一遍尤其是空数组、重复值、无解这三类。做完马上写复盘把“同类骨架的题号”记在一起隔两天重新做一遍。这条看起来笨实际效果很好。最后说一点个人体会。最开始我也觉得这两道题简单到没什么可写但真正把它们放在一起拆了一轮之后反而发现最基础的东西最值得反复咀嚼。我后来带刚入门的同学都会让他们把两题连着做并且强制自己回答一个问题如果我把“返回下标”改成“是否存在”解法会变成什么样子。能把这种改动回答清楚哈希表这一关才算真正过了。同时也提醒一句别急着追求题目数量把一个模式彻底吃透比草草刷完几十道题管用得多。这篇写完我自己又把存在重复元素的排序方案重新实现了一遍算是补上了当年“只写集合解法”留下的空档。

哈希表入门：两数之和与存在重复元素的同源解法

相关推荐

技能体系搭建与迭代：从识别、分层到组合变现

knowledge-work-plugins：知识工作流的声明式操作系统

REA缩写解析：技术项目命名中的语义锚定与上下文必要性

更多资讯

USB分析仪实战：HID设备偶发丢包的定位思路与排查方法

GeoScene异步GP服务调用实战：从超时到高并发稳定运行

企业级AI Agent如何安全接入遗留系统与数据孤岛

ArtCraft：可复现的创作方法论与参数化过程实践

Portal认证实战：组网模式、认证流程与配置避坑指南

程序化艺术工作流artcraft：从随机生成到可控创作

今日更新

微信云开发旅游小程序实战：LBS打卡+UGC社交全栈方案

金融AI代理平台核心拆解：从多代理协作到财报分析实战

基于大数据的智慧旅游推荐与可视化平台架构实践

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

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

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

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

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