1. 哈希表基础：搞清楚底层原理，比背题更重要

哈希表，也叫散列表，核心思想就是通过一个哈希函数，把要存储的键值映射到一个固定大小的数组下标上，从而实现O(1)的查找、插入和删除。你不需要遍历整个容器去找一个元素，直接通过计算就能定位到它，这就是它快的原因。

但哈希表不是万能的。第一，哈希函数有可能产生冲突，也就是两个不同的键被映射到了同一个下标，这叫哈希碰撞。第二，它的空间换时间特性决定了，如果数据量很小、键的范围很窄，直接用数组反而更划算，因为数组本身就是一种天然的哈希表，下标就是键，值是内容。很多新手一上来就抱着unordered_map不撒手，遇到所有查找问题都往里塞，这其实是没理解哈希表的适用边界。

在算法题这个场景里，哈希表的三种形态要分清楚：

• 数组：键是整数，且范围可控、数据量不大时首选。比如字符统计，键就是ASCII码，范围就26个字母，用数组开个长度26的哈希表，比用map省内存、速度快得多。
• set（集合）：只关心某个元素是否存在，不关心它出现了几次。适合去重、查重、取交集这类场景。
• map（映射）：键值对都要存，也就是既要记录哪个元素出现了，还要记录它出现了几次、出现在哪个位置等额外信息。

这一天的四道题，恰好按顺序覆盖了数组、set、map三种形态，你跟着刷下去，就能建立起一套“什么时候用什么”的判断逻辑，而不是每道题都靠背答案。

2. 242.有效的字母异位词：数组哈希打基础，字符串处理的入门题

2.1 先看懂题目在问什么

字母异位词，就是两个字符串用到的字母种类和数量完全一致，只是排列顺序不同。比如anagram和nagaram，都是由3个a、1个n、1个g、1个r、1个m组成的。反过来，rat和car，虽然都有字母a和r，但rat里没有c，car里没有t，数量对不上，所以不是异位词。

暴力解法是把两个字符串分别排序，然后逐位比较。这样做能过，但时间复杂度是O(n log n)，因为排序占了主导。对于这个题来说显然不是最优解——我们只需要知道字母的“组成”是否相同，根本不需要关心顺序，而排序恰恰是在处理顺序。

2.2 核心思路：用长度26的数组当哈希表

字母一共就26个，每个字母的ASCII码是一个连续整数，这天然满足“键范围小且可控”的条件。于是开一个长度26的数组record，下标0到25分别代表a到z。

遍历第一个字符串时，每遇到一个字符，就用record[ch - 'a']++把它对应的计数加一。遍历第二个字符串时，同样计算下标，用record[ch - 'a']--把计数减一。

最后看一遍整个数组，只要有一个位置不是0，就说明两个字符串中存在某个字母的数量不一致，返回false；全为0则返回true。

2.3 代码实现与易错点

class Solution { public: bool isAnagram(string s, string t) { int record[26] = {0}; // 必须初始化，否则里面是随机值 for (int i = 0; i < s.size(); i++) { record[s[i] - 'a']++; } for (int i = 0; i < t.size(); i++) { record[t[i] - 'a']--; } for (int i = 0; i < 26; i++) { if (record[i] != 0) { return false; } } return true; } };

不少人在第一次写的时候会犯同一个错误：忘记初始化数组。C++里局部变量int record[26];如果不在声明时写= {0}，数组元素是不确定的随机值。你后面的自增自减都是基于这个随机值做的，结果自然全错。这是我见过小白在哈希表题目里最容易踩的坑之一。

还有一个细节值得注意：s[i] - 'a'这个写法，本质上是利用了ASCII码的连续性。a到z的ASCII码是97到122，减去'a'（97）之后正好得到0到25的下标。这个技巧在涉及字符映射的题目里会反复出现，建议直接记成固定套路。

2.4 复杂度分析与进阶变形

时间复杂度O(n)，n是两个字符串中较长的那个的长度，因为要遍历完两个字符串加一个固定长度26的检查。空间复杂度O(1)，因为不管字符串多长，数组长度永远是26。

两道经典变形题值得在刷完这题之后顺手做掉：

• 383.赎金信：判断一个字符串能不能由另一个字符串里的字符组成，思路几乎一样，只是第二遍遍历时不能减出负数，因为每封信只能用一次杂志里的字符。
• 49.字母异位词分组：用排序后的字符串作为map的键，把异位词归到同一组，这道题会逼着你把哈希表的应用从“判断”提升到“分组”。

3. 349.两个数组的交集：set去重的实战场景

3.1 题目的隐藏要求

题目要求输出两个数组中同时出现的元素，而且每个元素只能出现一次。也就是说，nums1 = [1,2,2,1]和nums2 = [2,2]的结果是[2]，而不是[2,2]。

先去重，再判断是否存在，这两个需求叠加在一起，恰好指向了unordered_set。它内部的元素是唯一的，插入重复元素会自动失效。

3.2 为什么不用数组

这时候有人要问了，上一题用数组用得好好的，这题为什么不用数组？原因有两个：

1. 题目没有说明数组元素的范围，可能是负数，可能是跨度极大的整数。如果直接用元素值当下标，要么下标越界，要么数组开得巨大无比，浪费空间。
2. 即使你知道范围，如果数据非常稀疏，比如只有1和999999两个数，开一个百万长度的数组就为了存两个元素，显然不合理。

所以，当键的取值范围不确定或者过于分散时，就用unordered_set或unordered_map。所谓“哈希表”，本质上就是把键通过哈希函数映射到一个哈希桶数组上，由容器自动管理映射关系，你不需要关心具体的下标怎么算。

3.3 代码实现

class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> result_set; // 存放去重后的结果 unordered_set<int> nums_set(nums1.begin(), nums1.end()); // 直接把nums1去重并存入set for (int num : nums2) { if (nums_set.find(num) != nums_set.end()) { result_set.insert(num); } } return vector<int>(result_set.begin(), result_set.end()); } };

代码很直观：先把nums1转为set完成去重，再遍历nums2，逐个判断是否存在于set中，存在就插入结果集。结果集本身也是set，这样即使nums2里有多个重复元素也不会导致结果里出现重复。

Python版本更简洁：

class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: return list(set(nums1) & set(nums2))

set(nums1)去重，set(nums2)去重，取交集，转回列表，一行搞定。Python的集合运算本身就是哈希表在底层工作的结果。

3.4 进阶思考：有序数组也能用双指针

这题还有另一个方向——如果两个数组是有序的，可以用双指针各指一个数组，相等则加入结果，否则较小的那个指针向后移动。时间复杂度O(n + m)，而且不需要额外空间。但当数组无序时，哈希表的O(n)时间 + O(n)空间方案仍然是最直接、最不容易出错的解法。

我在实际刷题中还有一个体会：很多题目不是只有一种解法，关键是建立“先想清楚数据特征，再选择工具”的习惯。数组无序、元素范围可能很大、要求去重，看到这几个特征，就该想到set。

4. 202.快乐数：不是数学题，是哈希表判断循环

4.1 题目核心是一个无限循环问题

快乐数的定义是：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程，直到这个数变为1，或者无限循环但始终变不到1。

举个例子，19：

• 1² + 9² = 82
• 8² + 2² = 64
• 6² + 4² = 36
• 3² + 6² = 45
• 4² + 5² = 41
• 4² + 1² = 17
• 1² + 7² = 50
• 5² + 0² = 25
• 2² + 5² = 29
• 2² + 9² = 85
• 8² + 5² = 89
• 8² + 9² = 145
• 1² + 4² + 5² = 42
• 4² + 2² = 20
• 2² + 0² = 4
• 4² = 16
• 1² + 6² = 37
• 3² + 7² = 58
• 5² + 8² = 89

注意，89又出现了。这说明形成了一个循环，从这个点开始，后面的序列会一直绕圈，再也不会到1。所以19不是快乐数。

那怎么用程序判断有没有陷入循环？关键就是：当某个中间结果已经出现过一次，而这次又出现了，说明出现了环。这时候如果有哈希表记录历史出现过的数，一击即中。

4.2 代码实现

class Solution { public: int getSum(int n) { int sum = 0; while (n) { sum += (n % 10) * (n % 10); n /= 10; } return sum; } bool isHappy(int n) { unordered_set<int> seen; while (n != 1 && seen.find(n) == seen.end()) { seen.insert(n); n = getSum(n); } return n == 1; } };

getSum函数负责计算各位数字的平方和。注意n % 10取出个位，n /= 10去掉个位，直到n变为0，这个取数位的循环是基本功，写熟它。

主逻辑里，只要n没变成1，并且当前n没有在set中出现过，就继续迭代。一旦发现n已经在set里，说明进入循环了，立刻退出while循环，最后判断n是否等于1来返回结果。

4.3 一个关键细节：为什么不用数学推导

有经验的读者可能会想，这不是一个数学问题吗？如果能证明“非快乐数最终都会进入某个固定的循环”，是不是就不需要用哈希表了？

确实，数学上可以证明，所有非快乐数最终都会进入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4这个循环。你可以直接判断n == 4来加速，但这样做把问题特殊化了，失去了通用性。刷题的目的是掌握一类问题的解法，而不是为了单题的最优解去背一个数学结论。用哈希表记录历史状态，是一种通用的“检测是否重复出现”的手段，能解决一大类问题，环形链表、重复子串模板等都能用上。所以我更推荐用哈希表的思路来解这道题。

4.4 细节陷阱

• 如果输入n本身就是1，直接返回true，不需要进入循环。
• getSum要写成独立函数，主循环里只负责更新n和判断条件，逻辑更清晰。
• 不需要在set里插入1，因为1是终止条件，判断n == 1就够了。

5. 1.两数之和：map的经典场景，哈希表进阶必修

5.1 暴力解法为什么不行

题目是：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数的下标，假设每种输入只对应一个答案，同一个元素不能用两次。

最直接的暴力解法就是两层循环，每层各选一个下标，判断nums[i] + nums[j]是否等于target。时间复杂度O(n²)，在数组长度很大时难以接受。

暴力解法的效率瓶颈在于：对于每个nums[i]，你需要去数组剩余部分里“找”有没有target - nums[i]。这个“找”的过程是O(n)的线性扫描。如果能把“找”从O(n)降到O(1)，整个算法的时间复杂度就降到了O(n)。

5.2 为什么用map而不是set或数组

问题在于，你不仅需要知道target - nums[i]是否存在，还需要知道它的下标。set只能告诉你有或者没有，存不了下标信息。数组倒可以存下标，但前提是知道键的范围且不能太大，题目没说数组元素的范围，可能负数、可能上亿，所以数组不可用。

map的映射关系是元素值 -> 下标，正好满足需求。遍历数组时，对每个nums[i]，去map里找target - nums[i]，找到了就返回两个下标；没找到就把nums[i]和它的下标i存进map。

这里有一个极其重要的细节：先把当前值存进map还是先查map？

正确答案是：先查，后存。因为题目要求同一个元素不能用两次。如果先存再查，nums[i]很可能会在map里找到它自己。比如target = 6，nums[i] = 3，先存的话， map里立刻就有了键3，查询6 - 3 = 3就会命中自己，返回[i, i]，这是错误的。

5.3 代码实现

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> map; // 键是元素值，值是下标 for (int i = 0; i < nums.size(); i++) { int complement = target - nums[i]; auto it = map.find(complement); if (it != map.end()) { return {it->second, i}; } map.insert({nums[i], i}); // 当前值延后插入 } return {}; } };

Python版本：

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: seen = {} for i, num in enumerate(nums): complement = target - num if complement in seen: return [seen[complement], i] seen[num] = i return []

单次遍历就能完成，时间复杂度和空间复杂度都是O(n)。

5.4 同类问题的扩展思路

两数之和的变体很多，最典型的是15.三数之和。不过要注意，三数之和如果用哈希表来做会比较复杂，因为要去重，反而双指针法更简洁高效。这是一个非常有意思的对比：不是所有“多一个数”的题目都适合用哈希表硬解，学会判断各类做法的适用边界，比多刷几道题更重要。

6. 刷题避坑指南：哈希表相关的五个常见问题

6.1 数组下标越界与初始化

C++的数组不会自动越界检查，record[26]你写record[26]就是越界访问了。很多字符串题目中，如果字符中包含大写字母、空格或其他符号，你的ch - 'a'就可能算成负数或者超出25，导致下标越界。建议在写代码前先确认输入范围，或者统一用std::unordered_map<char, int>这种不容易越界的方式兜底，虽然性能差一些，但不容易崩。

需要再强调一遍的是，C++数组必须显式初始化，否则是随机值。

6.2 unordered_set和set别搞混

set底层是红黑树，unordered_set底层是哈希表。前者的查找、插入、删除是O(log n)，后者是O(1)平均。刷题默认优先用unordered_set，因为它更快。只有在需要有序遍历set中的元素时才用set。这个选择题在面试中也经常被问到，你得能说清楚底层区别。

6.3 哈希冲突不用自己处理

初学哈希表的时候，我一度很担心哈希冲突的问题，总觉得自己写的代码会因为在哈希桶里链太长而变慢。实际上，unordered_map和unordered_set内部已经处理好了冲突（一般用链地址法），你只需要关心用哪种容器、存什么键值就够了。如果哈希函数设计得很差导致大量冲突，C++标准库会做rehash，这是容器内部的事务，不需要我们操心。

6.4 用值当下标时，注意负数和溢出

数组哈希要求键是非负整数且范围可控。元素是负数的情况，可以先做一个偏移，比如所有值加1000再当下标，但这样就要考虑偏移量和最大值的边界，超出了就还是老实换用map或set。数值特别大时还要留意int溢出问题，nums[i] + target这种计算建议先转成long long或者换种写法，比如target - nums[i]。

6.5 不要忽视边界输入

刷题不能只盯着正常用例，边界情况往往就是面试官考察的重点。比如：数组为空、字符串长度不相同、target减去当前值等于当前值本身、数组中最大的两个数相加依然小于target等等。写代码前先在草稿纸上列几个边界用例，养成这个习惯之后，一次通过率会显著提升。

7. 做题顺序的价值：为什么哈希表要从数组到map逐步进阶

把这一天的四道题放在一起看，你会发现它们的做题顺序本身就是在教你哈希表的使用梯度。

242题用数组，因为键的范围是确定的26个字母，这是哈希表最原始、最高效的形态。349题用set，因为键的范围不好控制，但又只需要判断存在性，不需要存额外信息。202题用set检测循环，因为核心需求是“这个数出现过没有”，set是最直接的工具。1题用map，因为答案需要返回下标，必须存储键值对。

这四道题如果反过来做，先碰两数之和，再回头做字母异位词，你的思维就会被map局限住——遇到字符统计也下意识地开map，虽然也能做对，但性能差了一截。按这个顺序刷，其实就是刻意地训练你“用最小的工具解决问题”的思路。

很多人在刷题阶段容易犯一个毛病：只追求把题AC了，不看题解里更高效的方案。于是同一个解题套路用了很久，思维反而被固定住。我建议的做法是，每道题AC之后，至少再花十分钟看一两个高票题解，对比自己的解法和最优解的差距在哪里。是在数据结构的选择上，还是在循环条件的控制上？把这些差距记录下来，比盲刷五十道新题有用得多。

8. 现场排查实录：一次调试哈希表代码的真实经历

说一个我自己调试时的真实场景。某次在实际项目中需要快速判断一批字符串里有没有重复元素，我顺手写了个unordered_set的版本，结果在数据量接近百万级别时性能突然变得很差。排查了半天，才发现是因为我自定义的对象类型没有提供哈希函数，导致容器退化为用地址做哈希，冲突率暴涨，查找接近O(n)。

这个教训放到算法题里同样成立：C++的unordered_set和unordered_map对内置类型（int、string等）有默认哈希支持，但如果你自定义了结构体，就必须自己提供哈希函数和相等比较函数，否则性能会大打折扣。刷题虽然很少用到这一步，但面试如果追问“哈希表底层怎么实现的”“项目里怎么优化哈希表性能”，这恰恰是关键考点。

再分享一个更贴近题目的小坑。有一回我在本机调试两数之和，测试用例是nums = [3,2,4]，target = 6。我先存map后查找的版本返回了[0,0]，因为3 + 3 = 6，3在map里找到的下标是0，和当前下标0相同，满足题目返回条件但实际答案是错的。当场没看出来，因为示例里的重复情况很少见，但一旦数据里有重复值时，这种bug会非常隐蔽。所以先查后存这个顺序，不是细节，是正确性的关键，要在笔记本上标红。

调试技巧方面，我习惯在写循环时打印每一步map的键值对，看它有没有把异常数据存进去。一旦map里的键值对和你预期的一致，问题基本就出在循环顺序和条件判断上。哈希表这一类的bug都比较好定位，只要先把容器内容打出来，90%的问题都藏不住。

最后聊一点关于笔记的经验。后来的读者回看这个系列时，最好能自己整理一份哈希表选型速查表，拿到题先问自己三个问题：需要存键值对吗？键的范围确定吗？只关心元素是否存在吗？把这三个问题回答完，选型基本就不会错了。代码随想录这套题的编排巧妙之处也在这里，四道题刚好把三个分支怼到你面前，每道题都在逼你回答选型问题。刷透这一天，哈希表的底子就算打牢了。