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里没有ccar里没有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减去a97之后正好得到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和999999两个数开一个百万长度的数组就为了存两个元素显然不合理。所以当键的取值范围不确定或者过于分散时就用unordered_set或unordered_map。所谓“哈希表”本质上就是把键通过哈希函数映射到一个哈希桶数组上由容器自动管理映射关系你不需要关心具体的下标怎么算。3.3 代码实现class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { unordered_setint result_set; // 存放去重后的结果 unordered_setint 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 vectorint(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。举个例子191² 9² 828² 2² 646² 4² 363² 6² 454² 5² 414² 1² 171² 7² 505² 0² 252² 5² 292² 9² 858² 5² 898² 9² 1451² 4² 5² 424² 2² 202² 0² 44² 161² 6² 373² 7² 585² 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_setint 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 6nums[i] 3先存的话 map里立刻就有了键3查询6 - 3 3就会命中自己返回[i, i]这是错误的。5.3 代码实现class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, 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_mapchar, 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 63在map里找到的下标是0和当前下标0相同满足题目返回条件但实际答案是错的。当场没看出来因为示例里的重复情况很少见但一旦数据里有重复值时这种bug会非常隐蔽。所以先查后存这个顺序不是细节是正确性的关键要在笔记本上标红。调试技巧方面我习惯在写循环时打印每一步map的键值对看它有没有把异常数据存进去。一旦map里的键值对和你预期的一致问题基本就出在循环顺序和条件判断上。哈希表这一类的bug都比较好定位只要先把容器内容打出来90%的问题都藏不住。最后聊一点关于笔记的经验。后来的读者回看这个系列时最好能自己整理一份哈希表选型速查表拿到题先问自己三个问题需要存键值对吗键的范围确定吗只关心元素是否存在吗把这三个问题回答完选型基本就不会错了。代码随想录这套题的编排巧妙之处也在这里四道题刚好把三个分支怼到你面前每道题都在逼你回答选型问题。刷透这一天哈希表的底子就算打牢了。