看到系列第一讲把“两数之和”和“存在重复元素”摆在一起，我一开始是有点疑惑的。一道是配对查找，一道是去重检测，一个要返回下标，一个只给真假，怎么看都像两码事。直到我把两个答案并排写在纸上，才发现它们几乎是同一个知识点换了两张皮：都是在一遍遍历的过程里，用哈希表快速回答“这个数以前见过吗”。两数之和问的是“能跟我凑成 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 = 0，num = 3，diff = 3，此时seen是空的，查不到，于是把3:0放进去。第二步，i = 1，num = 3，diff = 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 里是set，Java 里是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 给初学者的几条具体建议
- 先亲手写一遍暴力解，再写优化解，不要直接背最优解。暴力解是理解的起点，也是正确性的基准。
- 用纸笔画一遍模拟过程，至少把两数之和按照三五个用例完整走一遍，不跳步，再动手写代码。
- 代码写完，把边界条件清单过一遍，尤其是空数组、重复值、无解这三类。
- 做完马上写复盘，把“同类骨架的题号”记在一起，隔两天重新做一遍。这条看起来笨，实际效果很好。
最后说一点个人体会。最开始我也觉得这两道题简单到没什么可写，但真正把它们放在一起拆了一轮之后，反而发现最基础的东西最值得反复咀嚼。我后来带刚入门的同学，都会让他们把两题连着做，并且强制自己回答一个问题：如果我把“返回下标”改成“是否存在”，解法会变成什么样子。能把这种改动回答清楚，哈希表这一关才算真正过了。同时也提醒一句，别急着追求题目数量，把一个模式彻底吃透，比草草刷完几十道题管用得多。这篇写完，我自己又把存在重复元素的排序方案重新实现了一遍，算是补上了当年“只写集合解法”留下的空档。
才告诉我问题出在第二章)
