刷算法题的人，大概率第一站就是两数之和；紧接着往哈希表方向多走一步，就会碰上存在重复元素。这两道题在很多在线评测平台上被标记为“简单”，但真正面试的时候，能把它们讲清楚的人远没有想象中多。我见过不少同学把解法背得滚瓜烂熟，被问到“为什么要用哈希表”“能不能不用额外空间”“如果数组有序怎么办”时，却一句话都接不上。这篇博文属于“算法一”系列的第一篇，我就把这两道高频题放在一起拆，因为它们的底层逻辑是同一个：用哈希表的 O(1) 查询，去解决“查询历史元素”的问题。我会从暴力解讲到最优解，把每一步的取舍和边界都交代清楚，再附上可以直接复制的代码和一份实战踩坑清单。适合刚开始刷算法、准备实习或校招的朋友，也适合那些背过答案但想真正理解原理的人。1. 两数之和：一道题把“空间换时间”演给你看1.1 读懂题目：别把“下标”和“值”搞混题目描述通常是这样的：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。注意几个关键词：返回下标，不是返回值；每种输入只会对应一个答案；同一个元素不能重复使用。很多初学者第一个坑就踩在“下标”上。我见过有人用排序后双指针解出了正确的值，但返回的时候直接返回排序后数组的下标，结果和原数组对不上，整个判题直接报错。还有一个坑是“同一个元素不能重复使用”，比如 nums=[3,3]，target=6，正确结果是 [0,1]，而不是 [0,0] 或者 [1,1]。这两个点看起来简单，但恰恰是后面所有优化方案的前提。理解题目时还要注意：数组可能是无序的；数组中可能有负数；可能存在重复值。只要保证“有且仅有一对答案”，我们就不用处理多解的情况，循环找到一个就可以立即返回。1.2 暴力解法：能过，但你没法跟面试官交代暴力解法是最直觉的：两层循环，外层固定一个数 i，内层从 i+1 开始找另一个数 j，判断 nums[i]+nums[j] 是否等于 target。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 []这段代码的正确性没问题，但时间复杂度是 O(n^2)。假设数组长度为 10 万，双层循环就是 50 亿次比较，在大多数在线评测平台上跑不完。为什么要从 i+1 开始而不是从 0 开始？因为我们要避免重复配对：i=0,j=1 和 i=1,j=0 是同一对，完全没必要算两次。同时也要防止 i=j，否则会把自己和自己加起来，比如 nums=[3,2,4], target=6，i=0 时 nums[0]=3 不对，但如果你允许 i=j，i=1 时 nums[1]=2 也不对，i=2 时 nums[2]=4 也不对，看起来没问题；换到 nums=[3,3], target=6，i=0, j=0 会直接返回 [0,0]，这就是错的。暴力解不是不能用，而是只能用来垫底。面试时你说“我想到的最笨方法是双重循环”，面试官通常会点头，然后追问“能不能优化”。所以暴力解的价值是提供一个起点，让你能往“查找更快”的方向思考。1.3 哈希表一次遍历：第一优先级的“记忆化”暴力解慢在每次都要在数组里重新扫一遍“历史元素”。如果能把历史和当前值的匹配 O(1) 完成，整体就能降到 O(n)。哈希表就是干这个的。具体思路很简单：遍历数组，对于当前值 num，我们需要知道在已经扫过的部分里，是否存在 target - num。如果存在，直接返回它的下标和当前下标；如果不存在，就把当前值以及它的下标存进哈希表，继续往后扫。我举一个例子：nums=[2,7,11,15]，target=9。i=0，num=2，target-num=7，哈希表是空的，于是记录 2 -> 0。i=1，num=7，target-num=2，在哈希表里查到了 2 对应的下标 0，返回 [0,1]。整个过程只需要一次遍历。这和“查字典”一样：你每到一个新词，先查字典里有没有能跟它组成短语的另一个词，没有就把它记到字典里，下一个人来翻就能找到。这里有一个极其重要的顺序问题：一定是先查，再存。你要是先把当前值存进去再查，就会出 bug。很多人栽在这上面，后面我单独讲。1.4 代码实现与逐行解读Python 版本：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 [] # 题目保证有解，这里只是兜底逐行说：seen = {}：创建空哈希表，key 是数组里的值，value 是对应的下标。enumerate(nums)：同时拿出下标和值。i是当前下标，num是当前值。diff = target - num：计算当前值需要搭配的另一个数。if diff in seen：检查这个互补数是否在前面出现过。return [seen[diff], i]：返回两个下标。因为seen[diff]一定是之前存进去的，下标一定小于当前的i，所以返回的数组天然是升序的。seen[num] = i：没有找到配对，就把当前值和下标记下来。如果要用其他语言，核心思想完全一样。C++ 版本如下：#include <vector> #include <unordered_map> std::vector<int> twoSum(std::vector<int>& nums, int target) { std::unordered_map<int, int> seen; for (int i = 0; i < nums.size(); ++i) { int diff = target - nums[i]; if (seen.find(diff) != seen.end()) { return {seen[diff], i}; } seen[nums[i]] = i; } return {}; }Java 的 HashMap、Go 的 map 也都是同样的套路。重点不是背某个语言的具体写法，而是记住“建表、查表、写表”这三步的顺序。1.5 复杂度分析和为什么不能“先存再查”时间复杂度：每个元素只需要处理一次，哈希表的读写平均是 O(1)，所以整体 O(n)。空间复杂度：最坏情况下数组里每个元素都要存进哈希表，所以 O(n)。但有个细节值得展开：哈希表不是神。散列冲突严重时，读写可能退化到 O(n)，这样整体就会变成 O(n^2)。不过在工程实践中，高级语言的哈希表实现都会处理冲突和扩容，平均性能仍然接近 O(1)。面试时你说“平均 O(1)”就够了，严谨一点可以补一句“最坏情况依赖哈希函数，但实际运行时接近 O(1)”。再回到“先查后存”。如果先存再查，会出现什么情况？看这个例子：nums=[3,3]，target=6。错误的做法：i=0 时，先把 nums[0]=3 存进哈希表，然后通过 diff=target-3=3，去哈希表里查 3，发现已经存在，返回 [0,0]。这显然不对，因为题目不允许同一个元素被用两次。正确的做法：i=0 时先查 diff=3，哈希表是空的，所以不返回，再存 3。i=1 时先查 diff=3，哈希表里有 3 对应下标 0，于是返回 [0,1]。这就是为什么“查必须发生在存之前”。有同学说，我可以先存，然后判断返回的下标不等于当前 i 就行。但那样会多一层判断，而且语义上不如“先查后存”清晰。面试时直接写“先查后存”是最稳的，不会给面试官留下把柄。2. 存在重复元素：从“排序思维”到“集合思维”2.1 题目本质：判断是否有“画等号”的机会存在重复元素的题面更短：给定一个整数数组，判断是否存在重复元素。如果任意一个值在数组中出现至少两次，返回 true；如果每个元素都互不相同，返回 false。拆开看，这个问题本质是问：数组里能不能找到两个下标 i 和 j，满足 i != j 且 nums[i] == nums[j]。它不关心下标，不关心顺序，只关心“有没有重复”。所以我们需要一种能快速告诉我们“这个值以前有没有出现过”的机制。和两数之和一样，数组本身给不出这种 O(1) 的回答，所以还得靠哈希思想。有一点容易被忽略：空数组或者只有一个元素的数组，直接返回 false。因为没有两个位置可以比较。好在大多数实现里，循环根本不会进入，自然返回 false，但你写代码时要意识到这个边界存在。2.2 排序解法：O(n log n) 换 O(1) 空间不借助额外空间的一种做法是先排序。排序之后，相等的元素会排在相邻位置。只要从左到右扫一遍，检查相邻两个数是否相等，就能判断有没有重复。def contains_duplicate_sort(nums): if len(nums) < 2: return False nums.sort() for i in range(len(nums) - 1): if nums[i] == nums[i + 1]: return True return False复杂度上，排序需要 O(n log n)，扫描相邻元素需要 O(n)，所以总时间是 O(n log n)。空间复杂度取决于排序算法是原地还是非原地。比如 Python 的 sort 是原地排序，额外空间通常很低；但如果用某些稳定排序并复制数组，最坏可能有 O(n) 空间。所以面试时不要拍胸脯说“排序一定是 O(1) 空间”，要加一句“如果使用原地排序的话”。这个解法最大的副作用是改变了原数组。如果题目后续还有别的需求，比如要保留原顺序，那你就得先拷贝一份再排序，空间复杂度就又上去了。面试时被问到“能不能不用额外空间”，排序方案是最自然的回答之一。不过如果面试官问“时间复杂度还能更低吗”，你就该转到哈希集合了。2.3 哈希集合解法：用 O(n) 空间换 O(n) 时间哈希集合和哈希表的区别是：集合只记录 key，不记录 value。因为存在重复元素只需要知道“这个值见过没有”，不需要存下标。def contains_duplicate_set(nums): seen = set() for num in nums: if num in seen: return True seen.add(num) return False过程很直白：遍历，查集合，有就 true，没有就 add。还有一种一行写法：def contains_duplicate_one_line(nums): return len(set(nums)) != len(nums)这行代码非常 Pythonic：set(nums) 去重，如果去重后的长度和原数组长度不一样，说明有重复。但我要提醒你，这种写法虽然短，却有两个隐藏代价：它会一次性把整个数组的集合构建完，即使重复元素出现在很靠前的位置，也要等数组全部遍历结束才能知道结果，无法提前返回。它会额外创建一个大集合，内存峰值比显式循环更高。如果数组超级大，可能出现内存被吃满的情况。所以在面试里，我会先写显式循环版本，等面试官问“有没有更简洁的写法”时，再补一句“Python 里可以一行搞定，但要注意内存峰值”。这能展示你对性能和工程细节的理解。2.4 性能对比与选择建议把三种思路放在一起看：解法时间复杂度空间复杂度是否修改原数组适用场景暴力双重循环O(n^2)O(1)否数据量极小排序后比较O(n log n)原地排序时 O(1)是内存受限，允许改动数组哈希集合O(n)O(n)否默认首选，适合大多数情况我的默认选择顺序是：能用哈希集合就用哈希集合，代码简单，时间最快。如果面试官明确说“不能用额外空间”，立刻转排序。如果数组元素都在一个很小的整数范围内，比如 0 到 100，那可以用一个长度 101 的布尔数组作为“自制哈希表”，空间 O(1)，时间也是 O(n)。这种方案不是空谈，而是真的会出现在面试追问里，因为它在“空间换时间”这条路上又多了一个 trade-off。3. 两题联动：哈希表到底解决哪类问题3.1 一张表看清两个题目的共同骨架很多初学者把这两道题当成两个孤立题目，其实它们的解题骨架非常像。题目查询对象需要记录的信息核心数据结构两数之和target - nums[i] 是否存在于历史中每个元素的值与下标的映射dict / unordered_map存在重复元素nums[i] 是否存在于历史中每个元素是否出现过set / unordered_set两数之和查的是“互补值”，存在重复元素查的是“自身”。一个需要记录下标，一个只需要记录存在性。但它们都回答同一个问题：给定一个当前值，我能不能在已经看到的所有元素里，以 O(1) 的时间找到某个特定值？这就是哈希表最核心的使用场景之一：把“扫描历史、寻找匹配”从 O(n) 降为 O(1)。你可以把它理解成“记忆化”：我每走一步，都把自己的信息登记在一个快速检索系统里，后面任何人来问，我都能立刻答出“有没有、在哪儿”。3.2 场景变化：有序数组、内存受限、数据范围有限面试官不会只满足于你会写标准解法，他们喜欢改条件看你的应变能力。这两个题就是绝佳的“改条件”试验场。如果两数之和的数组已经是排好序的，你可以用双指针：左指针指向开头，右指针指向结尾，看两数之和和 target 的大小关系，大于 target 就右指针左移，小于 target 就左指针右移。时间复杂度 O(n)，空间 O(1)。但注意，如果题目要求返回原始下标，排序后双指针就不适用了，因为你丢失了原下标，除非你额外记录每个元素原来的位置。如果存在重复元素情况下内存受限，排序是首选。如果连排序都担心递归栈空间，可以自己实现非递归的归并，或者干脆接受 O(n^2) 的暴力解，这要根据数据规模来决定。面试时主动问清楚数据规模，是加分项。如果数据范围有限，比如值都在一个整数区间内，可以用布尔数组代替哈希表。比如值范围是 0 到 1000，那开一个bool[1001]就能完成存在性查询。这就是为什么有的面试官会追问“你知道哈希表底层吗”，因为很多 POC 场景里，自制数组哈希表比语言内置的哈希表更快、更可控。3.3 从这两题延伸开的经典变形清单这两道题是“哈希表启蒙题”，把里面的思路吃透，后面一大片中档题都能看到它们的影子。三数之和：固定一个数，剩下的问题退化成两数之和，通常用排序+双指针把 O(n^2) 搞定。最长无重复子串：滑动窗口 + 哈希集合，判断窗口内是否出现重复字符，本质就是在问“这个字符出现过没有”。两个数组的交集：用哈希集合记录第一个数组出现过的值，再遍历第二个数组查交集。字母异位词分组：把每个字符串排序后的结果作为 key，或者统计字符出现次数作为 key，底层还是哈希表。快乐数：不断计算平方和，如果出现了重复的数字，就说明进入了循环，这其实就是存在重复元素问题。所以不要小看这两道“简单题”。它们把“查询历史元素”这个高频模型压缩到了最简形态。你如果能把它们的思维过程讲清楚，后面遇到“判断循环”“查找配对”“去重计数”这三类问题，都会豁然开朗。4. 实际刷题中的坑与面试追问实录4.1 五个我亲眼见过的翻车现场先说翻车，因为翻车案例比标准答案更有教学价值。第一个翻车：函数末尾没有返回值。有些同学写两数之和时，循环里一旦找到就 return，循环外却什么都没写。在 Python 里会隐式返回 None，在 C++ 里有些编译器会警告但没有强制报错，在线评测可能直接判定运行时错误。虽然题目保证有解，但编译器并不知道。养成习惯，函数末尾兜底返回一个空数组或 false。第二个翻车：用 list 来代替哈希表。比如 Python 里写if target - num in nums，这个in nums对 list 来说是线性查找，表面上是 O(n) 循环，实际上每一轮又做了 O(n) 查找，整体还是 O(n^2)。很多同学提交后超时，百思不得其解，其实就是因为没用 set 或 dict。第三个翻车：两数之和先存再查。这个前面已经详细展开过，[3,3] 的例子能让人记一辈子。第四个翻车：存在重复元素用排序解法，但忘了原数组被修改。比如你先调用排序判重，后面还要用原数组顺序做其他统计，结果发现原数组已经变了。这种 bug 很隐蔽，因为代码本身不报错，只是逻辑结果错。第五个翻车：一行写法len(set(nums)) != len(nums)被面试官追问“如果数据量大到内存放不下怎么办”，答不上来。不是这行代码有问题，而是你没有主动讲出它的代价。面试比较的是理解深度，不是代码长度。4.2 面试官最常抛出的追问与参考答案我把常见的追问整理成速查，每一题都值得多想几分钟：追问参考答案要点数组有序时两数之和还能优化吗？可以，用双指针从两端向中间移动，O(n) 时间、O(1) 空间；但注意要返回原下标时排序会破坏索引。为什么哈希表查找是 O(1)？通过哈希函数直接定位桶，平均 O(1)；最坏哈希冲突可能退化，但现代实现会扩容和优化冲突策略。存在重复元素不允许用额外空间怎么办？排序后比较相邻元素；如果原地排序，额外空间 O(1)。数据范围是很小的整数，能更快吗？用固定长度的布尔数组或位图作为哈希表，时间 O(n)，空间 O(range)，本质还是哈希思想。数据量远超内存，怎么判重？先外部排序再扫描；或者分桶写入磁盘，每个桶内部去重；也可以用基于哈希的分布式聚合，看具体场景。这些问题考察的不是你对题目本身背得多熟，而是你是否真的理解“为什么用哈希表”。理解了底层逻辑，这些追问都能现场推出来。4.3 刷题方法论：这两道题之后该做什么对于新手，我的建议是不要急着刷更多新题。把这两道题吃透，比囫囵吞下二十道题有用得多。具体的操作路径是这样：第一步，关掉答案，手写暴力解，并分析暴力解为什么慢。这一步是建立“性能敏感”的直觉。第二步，写哈希解，同时用一个小例子手动走一遍，比如 [3,3] 这个 case 一定要走，确认“先查后存”没有 bug。第三步，在笔记里写两行总结：这题卡在哪？如果把数据变大、变小、变有序，解法会怎么变？这两行笔记是你以后面试复习的精华。第四步，隔一周再手写一遍。如果你还能顺畅地写出哈希解，并且能解释清楚“为什么不用先存再查”，说明你真的理解了。之后再去刷三数之和、最长无重复子串，你会发现很多套路是相通的。我个人在刷题早期走过一段弯路，总觉得要刷够各种标签、各种难度才安心，结果每道题都是背答案，两周后面试官换个数字我就懵了。后来我改变策略，把高频题反复嚼，一道题从暴力到最优、从标准条件到变形条件全走一遍，效果反而好很多。两数之和和存在重复元素就是最好的起点：它们简单到不会被吓退，又复杂到足够引出一整套“空间换时间”的思维方式。这套“算法一”系列，后续还会继续拆更多高频题。但无论拆到哪一题，我都建议你先回头看看这两道题里学到的哈希表思维。毕竟，刷题不是为了记住一百个答案，而是为了在面对没见过的题时，能快速判断出它到底在考什么。
刷算法题的人，大概率第一站就是两数之和；紧接着往哈希表方向多走一步，就会碰上存在重复元素。这两道题在很多在线评测平台上被标记为“简单”，但真正面试的时候，能把它们讲清楚的人远没有想象中多。我见过不少同学把解法背得滚瓜烂熟，被问到“为什么要用哈希表”“能不能不用额外空间”“如果数组有序怎么办”时，却一句话都接不上。这篇博文属于“算法一”系列的第一篇，我就把这两道高频题放在一起拆，因为它们的底层逻辑是同一个：用哈希表的 O(1) 查询，去解决“查询历史元素”的问题。我会从暴力解讲到最优解，把每一步的取舍和边界都交代清楚，再附上可以直接复制的代码和一份实战踩坑清单。适合刚开始刷算法、准备实习或校招的朋友，也适合那些背过答案但想真正理解原理的人。1. 两数之和：一道题把“空间换时间”演给你看1.1 读懂题目：别把“下标”和“值”搞混题目描述通常是这样的：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。注意几个关键词：返回下标，不是返回值；每种输入只会对应一个答案；同一个元素不能重复使用。很多初学者第一个坑就踩在“下标”上。我见过有人用排序后双指针解出了正确的值，但返回的时候直接返回排序后数组的下标，结果和原数组对不上，整个判题直接报错。还有一个坑是“同一个元素不能重复使用”，比如 nums=[3,3]，target=6，正确结果是 [0,1]，而不是 [0,0] 或者 [1,1]。这两个点看起来简单，但恰恰是后面所有优化方案的前提。理解题目时还要注意：数组可能是无序的；数组中可能有负数；可能存在重复值。只要保证“有且仅有一对答案”，我们就不用处理多解的情况，循环找到一个就可以立即返回。1.2 暴力解法：能过，但你没法跟面试官交代暴力解法是最直觉的：两层循环，外层固定一个数 i，内层从 i+1 开始找另一个数 j，判断 nums[i]+nums[j] 是否等于 target。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 []这段代码的正确性没问题，但时间复杂度是 O(n^2)。假设数组长度为 10 万，双层循环就是 50 亿次比较，在大多数在线评测平台上跑不完。为什么要从 i+1 开始而不是从 0 开始？因为我们要避免重复配对：i=0,j=1 和 i=1,j=0 是同一对，完全没必要算两次。同时也要防止 i=j，否则会把自己和自己加起来，比如 nums=[3,2,4], target=6，i=0 时 nums[0]=3 不对，但如果你允许 i=j，i=1 时 nums[1]=2 也不对，i=2 时 nums[2]=4 也不对，看起来没问题；换到 nums=[3,3], target=6，i=0, j=0 会直接返回 [0,0]，这就是错的。暴力解不是不能用，而是只能用来垫底。面试时你说“我想到的最笨方法是双重循环”，面试官通常会点头，然后追问“能不能优化”。所以暴力解的价值是提供一个起点，让你能往“查找更快”的方向思考。1.3 哈希表一次遍历：第一优先级的“记忆化”暴力解慢在每次都要在数组里重新扫一遍“历史元素”。如果能把历史和当前值的匹配 O(1) 完成，整体就能降到 O(n)。哈希表就是干这个的。具体思路很简单：遍历数组，对于当前值 num，我们需要知道在已经扫过的部分里，是否存在 target - num。如果存在，直接返回它的下标和当前下标；如果不存在，就把当前值以及它的下标存进哈希表，继续往后扫。我举一个例子：nums=[2,7,11,15]，target=9。i=0，num=2，target-num=7，哈希表是空的，于是记录 2 -> 0。i=1，num=7，target-num=2，在哈希表里查到了 2 对应的下标 0，返回 [0,1]。整个过程只需要一次遍历。这和“查字典”一样：你每到一个新词，先查字典里有没有能跟它组成短语的另一个词，没有就把它记到字典里，下一个人来翻就能找到。这里有一个极其重要的顺序问题：一定是先查，再存。你要是先把当前值存进去再查，就会出 bug。很多人栽在这上面，后面我单独讲。1.4 代码实现与逐行解读Python 版本：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 [] # 题目保证有解，这里只是兜底逐行说：seen = {}：创建空哈希表，key 是数组里的值，value 是对应的下标。enumerate(nums)：同时拿出下标和值。i是当前下标，num是当前值。diff = target - num：计算当前值需要搭配的另一个数。if diff in seen：检查这个互补数是否在前面出现过。return [seen[diff], i]：返回两个下标。因为seen[diff]一定是之前存进去的，下标一定小于当前的i，所以返回的数组天然是升序的。seen[num] = i：没有找到配对，就把当前值和下标记下来。如果要用其他语言，核心思想完全一样。C++ 版本如下：#include <vector> #include <unordered_map> std::vector<int> twoSum(std::vector<int>& nums, int target) { std::unordered_map<int, int> seen; for (int i = 0; i < nums.size(); ++i) { int diff = target - nums[i]; if (seen.find(diff) != seen.end()) { return {seen[diff], i}; } seen[nums[i]] = i; } return {}; }Java 的 HashMap、Go 的 map 也都是同样的套路。重点不是背某个语言的具体写法，而是记住“建表、查表、写表”这三步的顺序。1.5 复杂度分析和为什么不能“先存再查”时间复杂度：每个元素只需要处理一次，哈希表的读写平均是 O(1)，所以整体 O(n)。空间复杂度：最坏情况下数组里每个元素都要存进哈希表，所以 O(n)。但有个细节值得展开：哈希表不是神。散列冲突严重时，读写可能退化到 O(n)，这样整体就会变成 O(n^2)。不过在工程实践中，高级语言的哈希表实现都会处理冲突和扩容，平均性能仍然接近 O(1)。面试时你说“平均 O(1)”就够了，严谨一点可以补一句“最坏情况依赖哈希函数，但实际运行时接近 O(1)”。再回到“先查后存”。如果先存再查，会出现什么情况？看这个例子：nums=[3,3]，target=6。错误的做法：i=0 时，先把 nums[0]=3 存进哈希表，然后通过 diff=target-3=3，去哈希表里查 3，发现已经存在，返回 [0,0]。这显然不对，因为题目不允许同一个元素被用两次。正确的做法：i=0 时先查 diff=3，哈希表是空的，所以不返回，再存 3。i=1 时先查 diff=3，哈希表里有 3 对应下标 0，于是返回 [0,1]。这就是为什么“查必须发生在存之前”。有同学说，我可以先存，然后判断返回的下标不等于当前 i 就行。但那样会多一层判断，而且语义上不如“先查后存”清晰。面试时直接写“先查后存”是最稳的，不会给面试官留下把柄。2. 存在重复元素：从“排序思维”到“集合思维”2.1 题目本质：判断是否有“画等号”的机会存在重复元素的题面更短：给定一个整数数组，判断是否存在重复元素。如果任意一个值在数组中出现至少两次，返回 true；如果每个元素都互不相同，返回 false。拆开看，这个问题本质是问：数组里能不能找到两个下标 i 和 j，满足 i != j 且 nums[i] == nums[j]。它不关心下标，不关心顺序，只关心“有没有重复”。所以我们需要一种能快速告诉我们“这个值以前有没有出现过”的机制。和两数之和一样，数组本身给不出这种 O(1) 的回答，所以还得靠哈希思想。有一点容易被忽略：空数组或者只有一个元素的数组，直接返回 false。因为没有两个位置可以比较。好在大多数实现里，循环根本不会进入，自然返回 false，但你写代码时要意识到这个边界存在。2.2 排序解法：O(n log n) 换 O(1) 空间不借助额外空间的一种做法是先排序。排序之后，相等的元素会排在相邻位置。只要从左到右扫一遍，检查相邻两个数是否相等，就能判断有没有重复。def contains_duplicate_sort(nums): if len(nums) < 2: return False nums.sort() for i in range(len(nums) - 1): if nums[i] == nums[i + 1]: return True return False复杂度上，排序需要 O(n log n)，扫描相邻元素需要 O(n)，所以总时间是 O(n log n)。空间复杂度取决于排序算法是原地还是非原地。比如 Python 的 sort 是原地排序，额外空间通常很低；但如果用某些稳定排序并复制数组，最坏可能有 O(n) 空间。所以面试时不要拍胸脯说“排序一定是 O(1) 空间”，要加一句“如果使用原地排序的话”。这个解法最大的副作用是改变了原数组。如果题目后续还有别的需求，比如要保留原顺序，那你就得先拷贝一份再排序，空间复杂度就又上去了。面试时被问到“能不能不用额外空间”，排序方案是最自然的回答之一。不过如果面试官问“时间复杂度还能更低吗”，你就该转到哈希集合了。2.3 哈希集合解法：用 O(n) 空间换 O(n) 时间哈希集合和哈希表的区别是：集合只记录 key，不记录 value。因为存在重复元素只需要知道“这个值见过没有”，不需要存下标。def contains_duplicate_set(nums): seen = set() for num in nums: if num in seen: return True seen.add(num) return False过程很直白：遍历，查集合，有就 true，没有就 add。还有一种一行写法：def contains_duplicate_one_line(nums): return len(set(nums)) != len(nums)这行代码非常 Pythonic：set(nums) 去重，如果去重后的长度和原数组长度不一样，说明有重复。但我要提醒你，这种写法虽然短，却有两个隐藏代价：它会一次性把整个数组的集合构建完，即使重复元素出现在很靠前的位置，也要等数组全部遍历结束才能知道结果，无法提前返回。它会额外创建一个大集合，内存峰值比显式循环更高。如果数组超级大，可能出现内存被吃满的情况。所以在面试里，我会先写显式循环版本，等面试官问“有没有更简洁的写法”时，再补一句“Python 里可以一行搞定，但要注意内存峰值”。这能展示你对性能和工程细节的理解。2.4 性能对比与选择建议把三种思路放在一起看：解法时间复杂度空间复杂度是否修改原数组适用场景暴力双重循环O(n^2)O(1)否数据量极小排序后比较O(n log n)原地排序时 O(1)是内存受限，允许改动数组哈希集合O(n)O(n)否默认首选，适合大多数情况我的默认选择顺序是：能用哈希集合就用哈希集合，代码简单，时间最快。如果面试官明确说“不能用额外空间”，立刻转排序。如果数组元素都在一个很小的整数范围内，比如 0 到 100，那可以用一个长度 101 的布尔数组作为“自制哈希表”，空间 O(1)，时间也是 O(n)。这种方案不是空谈，而是真的会出现在面试追问里，因为它在“空间换时间”这条路上又多了一个 trade-off。3. 两题联动：哈希表到底解决哪类问题3.1 一张表看清两个题目的共同骨架很多初学者把这两道题当成两个孤立题目，其实它们的解题骨架非常像。题目查询对象需要记录的信息核心数据结构两数之和target - nums[i] 是否存在于历史中每个元素的值与下标的映射dict / unordered_map存在重复元素nums[i] 是否存在于历史中每个元素是否出现过set / unordered_set两数之和查的是“互补值”，存在重复元素查的是“自身”。一个需要记录下标，一个只需要记录存在性。但它们都回答同一个问题：给定一个当前值，我能不能在已经看到的所有元素里，以 O(1) 的时间找到某个特定值？这就是哈希表最核心的使用场景之一：把“扫描历史、寻找匹配”从 O(n) 降为 O(1)。你可以把它理解成“记忆化”：我每走一步，都把自己的信息登记在一个快速检索系统里，后面任何人来问，我都能立刻答出“有没有、在哪儿”。3.2 场景变化：有序数组、内存受限、数据范围有限面试官不会只满足于你会写标准解法，他们喜欢改条件看你的应变能力。这两个题就是绝佳的“改条件”试验场。如果两数之和的数组已经是排好序的，你可以用双指针：左指针指向开头，右指针指向结尾，看两数之和和 target 的大小关系，大于 target 就右指针左移，小于 target 就左指针右移。时间复杂度 O(n)，空间 O(1)。但注意，如果题目要求返回原始下标，排序后双指针就不适用了，因为你丢失了原下标，除非你额外记录每个元素原来的位置。如果存在重复元素情况下内存受限，排序是首选。如果连排序都担心递归栈空间，可以自己实现非递归的归并，或者干脆接受 O(n^2) 的暴力解，这要根据数据规模来决定。面试时主动问清楚数据规模，是加分项。如果数据范围有限，比如值都在一个整数区间内，可以用布尔数组代替哈希表。比如值范围是 0 到 1000，那开一个bool[1001]就能完成存在性查询。这就是为什么有的面试官会追问“你知道哈希表底层吗”，因为很多 POC 场景里，自制数组哈希表比语言内置的哈希表更快、更可控。3.3 从这两题延伸开的经典变形清单这两道题是“哈希表启蒙题”，把里面的思路吃透，后面一大片中档题都能看到它们的影子。三数之和：固定一个数，剩下的问题退化成两数之和，通常用排序+双指针把 O(n^2) 搞定。最长无重复子串：滑动窗口 + 哈希集合，判断窗口内是否出现重复字符，本质就是在问“这个字符出现过没有”。两个数组的交集：用哈希集合记录第一个数组出现过的值，再遍历第二个数组查交集。字母异位词分组：把每个字符串排序后的结果作为 key，或者统计字符出现次数作为 key，底层还是哈希表。快乐数：不断计算平方和，如果出现了重复的数字，就说明进入了循环，这其实就是存在重复元素问题。所以不要小看这两道“简单题”。它们把“查询历史元素”这个高频模型压缩到了最简形态。你如果能把它们的思维过程讲清楚，后面遇到“判断循环”“查找配对”“去重计数”这三类问题，都会豁然开朗。4. 实际刷题中的坑与面试追问实录4.1 五个我亲眼见过的翻车现场先说翻车，因为翻车案例比标准答案更有教学价值。第一个翻车：函数末尾没有返回值。有些同学写两数之和时，循环里一旦找到就 return，循环外却什么都没写。在 Python 里会隐式返回 None，在 C++ 里有些编译器会警告但没有强制报错，在线评测可能直接判定运行时错误。虽然题目保证有解，但编译器并不知道。养成习惯，函数末尾兜底返回一个空数组或 false。第二个翻车：用 list 来代替哈希表。比如 Python 里写if target - num in nums，这个in nums对 list 来说是线性查找，表面上是 O(n) 循环，实际上每一轮又做了 O(n) 查找，整体还是 O(n^2)。很多同学提交后超时，百思不得其解，其实就是因为没用 set 或 dict。第三个翻车：两数之和先存再查。这个前面已经详细展开过，[3,3] 的例子能让人记一辈子。第四个翻车：存在重复元素用排序解法，但忘了原数组被修改。比如你先调用排序判重，后面还要用原数组顺序做其他统计，结果发现原数组已经变了。这种 bug 很隐蔽，因为代码本身不报错，只是逻辑结果错。第五个翻车：一行写法len(set(nums)) != len(nums)被面试官追问“如果数据量大到内存放不下怎么办”，答不上来。不是这行代码有问题，而是你没有主动讲出它的代价。面试比较的是理解深度，不是代码长度。4.2 面试官最常抛出的追问与参考答案我把常见的追问整理成速查，每一题都值得多想几分钟：追问参考答案要点数组有序时两数之和还能优化吗？可以，用双指针从两端向中间移动，O(n) 时间、O(1) 空间；但注意要返回原下标时排序会破坏索引。为什么哈希表查找是 O(1)？通过哈希函数直接定位桶，平均 O(1)；最坏哈希冲突可能退化，但现代实现会扩容和优化冲突策略。存在重复元素不允许用额外空间怎么办？排序后比较相邻元素；如果原地排序，额外空间 O(1)。数据范围是很小的整数，能更快吗？用固定长度的布尔数组或位图作为哈希表，时间 O(n)，空间 O(range)，本质还是哈希思想。数据量远超内存，怎么判重？先外部排序再扫描；或者分桶写入磁盘，每个桶内部去重；也可以用基于哈希的分布式聚合，看具体场景。这些问题考察的不是你对题目本身背得多熟，而是你是否真的理解“为什么用哈希表”。理解了底层逻辑，这些追问都能现场推出来。4.3 刷题方法论：这两道题之后该做什么对于新手，我的建议是不要急着刷更多新题。把这两道题吃透，比囫囵吞下二十道题有用得多。具体的操作路径是这样：第一步，关掉答案，手写暴力解，并分析暴力解为什么慢。这一步是建立“性能敏感”的直觉。第二步，写哈希解，同时用一个小例子手动走一遍，比如 [3,3] 这个 case 一定要走，确认“先查后存”没有 bug。第三步，在笔记里写两行总结：这题卡在哪？如果把数据变大、变小、变有序，解法会怎么变？这两行笔记是你以后面试复习的精华。第四步，隔一周再手写一遍。如果你还能顺畅地写出哈希解，并且能解释清楚“为什么不用先存再查”，说明你真的理解了。之后再去刷三数之和、最长无重复子串，你会发现很多套路是相通的。我个人在刷题早期走过一段弯路，总觉得要刷够各种标签、各种难度才安心，结果每道题都是背答案，两周后面试官换个数字我就懵了。后来我改变策略，把高频题反复嚼，一道题从暴力到最优、从标准条件到变形条件全走一遍，效果反而好很多。两数之和和存在重复元素就是最好的起点：它们简单到不会被吓退，又复杂到足够引出一整套“空间换时间”的思维方式。这套“算法一”系列，后续还会继续拆更多高频题。但无论拆到哪一题，我都建议你先回头看看这两道题里学到的哈希表思维。毕竟，刷题不是为了记住一百个答案，而是为了在面对没见过的题时，能快速判断出它到底在考什么。