1. 《代码随想录》day5哈希表专题开篇刷到《代码随想录》第五天的时候明显感觉节奏开始变了。前四天还在数组、链表这些线性结构里打转到了day5直接切入一个全新的数据结构主题——哈希表。这一天一共四道题都来自力扣242.有效的字母异位词、349.两个数组的交集、202.快乐数、1.两数之和。题量不大但信息量很足哈希表的三种基本形态数组、set、map在四道题里轮番出场等于把这一块的基础框架一次性搭明白了。如果你正在跟这个题单刷题我可以直接告诉你结论day5是整个哈希表章节的入口把这四道题吃透后面关于哈希表的难题基本都是在这套思路上做变体。如果你是刚开始接触算法的非科班选手这里也是你第一次系统性接触“用空间换时间”这个概念的地方值得认真停下来咀嚼而不是急着把题过一遍就完事。这篇文章我打算从整体设计思路、哈希表核心原理、四道题的逐题拆解、常见坑点四个方向来复盘。不会只贴标准答案重点是把每一步选择背后的“为什么”讲清楚包括我在实际刷题和调试过程中遇到的那些课堂讲义上不会写的细节。无论你是第一天刷题还是已经刷了一阵子想回头夯实基础这篇应该都能给你一些参考。2. 哈希表专题的整体学习思路2.1 为什么第五天要把哈希表单独拎出来先理解《代码随想录》的编排逻辑。前四天安排的是数组和链表核心训练点是“遍历”、“指针移动”和“边界处理”。到了第五天引入哈希表实际上是给你引入一种新的思维方式不通过比较而是通过“直接定位”来解决问题。举个例子。数组里找某个元素最朴素的做法是遍历复杂度是O(n)但如果这个数组是一个“用下标当key”的结构我们就能在O(1)时间里直接定位。哈希表干的事情就是把任意类型的key字符、字符串、数字转换成数组下标这样“可以直接访问”的形式。这个思想从day5开始会一直贯穿到后面的滑动窗口、前缀和、图论相关题目里。Carl在题单里把哈希表安排在数组和链表之后也是因为它建立在前两者的基础上你需要先熟悉“元素-下标”的对应关系才能理解哈希函数把key映射成index这件事。而且前四天练的那些边界控制能力在写哈希表代码时同样用得上。2.2 哈希结构三兄弟数组、set、map怎么选很多初学者第一反应是“哈希表不就是HashMap吗”但实际刷题时你会发现哈希表在不同场景下要选用不同的数据结构。day5的四道题刚好覆盖了三种选择数据结构底层实现适用场景day5对应题目数组连续的存储空间key的范围已知且较小242.有效的字母异位词unordered_set哈希表只需要判断元素是否存在不需要记录个数349.两个数组的交集、202.快乐数unordered_map哈希表既要判断存在又要存放下标或次数1.两数之和选型依据其实可以浓缩成一句话查什么、查到之后还要不要用附属信息。只查“存不存在”就用set查“存在且还要取出另一个值”就用map如果key本身就是有限且密集的整数/字符范围直接用数组更快更省。我第一次刷到242题的时候第一反应也是“用两个map统计字符次数不就行了”但看完Carl的讲解才知道对于26个小写字母这个固定范围用一个长度为26的数组就够了代码更简单速度也更快。这就是《代码随想录》常说的“数组是哈希表里最容易被忽视但最高效的形态”。3. 核心方法拆解哈希函数、冲突处理与代码实现3.1 哈希函数到底做了什么哈希表的核心是一个哈希函数它做的工作就是把任意key映射到一个固定范围内的数字。你可以把它想象成一个储物柜系统每个柜子有一个编号你把东西存进去的时候管理员根据你的名字计算出编号取的时候用同样算法再算一遍编号直接开柜子不需要一个个柜子找。在算法题里这个“计算编号”的动作往往是隐式的。比如242题里字符c映射到下标就是c - a把字母转成0到25的数字比如快乐数里对数字做“各位平方和”本质也是在把一个数映射到另一个数。你不需要自己写一个复杂哈希函数但要理解这种“映射”思维——把数据样本空间压缩到可控范围同时保证映射后仍能区分不同的key。3.2 哈希碰撞拉链法和线性探测法当两个不同的key算出了同一个下标就发生了哈希碰撞。在工程实现里常见做法是拉链法同一个下标挂一个链表和线性探测法冲突了就往后找空位。C的unordered_set/unordered_map底层就是哈希表加链表结构发生碰撞时多个元素会挂在同一个桶上。刷算法题时你基本不用手写碰撞处理但有一个坑必须知道自定义类型比如pair、vector放进unordered_set时需要自己提供哈希函数和相等比较逻辑。day5的题都还不需要但如果后面你刷到需要用自定义key的题时会回来感谢这一条提醒的。3.3 数组模拟哈希的边界与局限数组作为哈希结构最大的优势是没有额外的哈希函数开销下标就是天然的key。但它的局限也明显key的范围不能太大。比如349题两个数组的交集如果数值范围扩展到10^9你就不能用数组模拟了因为根本开不出那么大的数组。这时候应该转而使用unordered_set它只会为实际出现的元素分配空间。另外还有一个细节数组模拟哈希时下标语义要想清楚。242题里record的下标代表“哪个字母”值代表“出现次数差”。把“键”和“值”的角色分清楚写出来的代码才不会绕晕。我只见过太多人在这一步下标越界、语义混用调试半天发现原来是把record[s[i] - a]写成了record[s[i]]——s[i]本身是字符不能直接当数组下标用。4. 四道题目逐题拆解思路、代码与易错点4.1 LeetCode 242 有效的字母异位词数组模拟哈希的教科书题目要求判断两个字符串是否包含相同字符且每个字符出现次数相同。比如s anagramt nagaram返回trues ratt car返回false。解题思路因为题目只涉及小写字母字符集是确定的26个用长度为26的数组记录每个字符的出现次数。先遍历s记录每个字母出现次数再遍历t对每个字母做减法最后检查数组是否全部为0。如果中间出现负数那说明t中某个字符比s多也可以提前返回false。class Solution { public: bool isAnagram(string s, string t) { int record[26] {0}; for (char c : s) { record[c - a]; } for (char c : t) { record[c - a]--; } for (int i 0; i 26; i) { if (record[i] ! 0) return false; } return true; } };时间复杂度O(n)空间复杂度O(1)因为数组大小固定。这里的“空间复杂度O(1)”是面试时容易被追问的点虽然用了record数组但它不随输入规模增长所以是常数级。我的实操心得第一次写这道题我用了两个map分别统计再比较逻辑也对但代码比数组写法长跑起来也慢。刷完这道题后我去查了C里map和unordered_map的区别map是有序的红黑树查找O(logn)unordered_map是哈希表平均O(1)。虽然这道题用哪个都能过但理解底层差异对选型很重要。另一个容易踩的坑是字符范围。如果题目扩展成包含所有ASCII字符数组长度就要改成256如果包含Unicode数组就不适用了。读题时一定要先看字符集约定。4.2 LeetCode 349 两个数组的交集set去重的典型场景题目要求给定两个数组输出它们的交集结果中每个元素唯一。解题思路把nums1的所有元素存进一个unordered_set然后遍历nums2如果当前元素在set里出现过就加入结果set。最后把结果set转成vector返回。用set而不是数组的原因题目没有给出数值范围虽然力扣的测试数据在0到1000之间但你不应该依赖这个隐含条件set的适用面更广。class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { unordered_setint result_set; unordered_setint nums_set(nums1.begin(), nums1.end()); for (int num : nums2) { if (nums_set.find(num) ! nums_set.end()) { result_set.insert(num); } } return vectorint(result_set.begin(), result_set.end()); } };时间复杂度O(mn)空间复杂度O(m)存nums1去重后的元素。踩过的坑我第一次没有用result_set做二次去重而是直接把匹配到的元素push到一个vector里结果nums2里如果有重复元素交集就会出现重复值。后来才意识到“输出结果去重”和“比较时去重”是两个不同环节。用set做结果容器天然就解决了这个问题。如果你非要用vector存结果那在插入前还需要判断result里是否已经存在该元素或者最后再对vector去重一次麻烦得多。4.3 LeetCode 202 快乐数哈希表检测循环的经典应用题目要求对一个正整数不断替换为它各位数字的平方和如果最终能变为1就是快乐数如果进入循环则不是。解题思路这个题的精髓在于“如何判断循环”。经历过的平方和结果如果再次出现说明进入了死循环。因此用unordered_set记录每次计算出的平方和只要新的sum已经在set中出现过就返回false。如果sum变为1返回true。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 set; while (true) { int sum getSum(n); if (sum 1) return true; if (set.find(sum) ! set.end()) return false; set.insert(sum); n sum; } } };关键点解析getSum函数是这道题里的核心工具每次取模10得到个位数字平方累加然后除以10去掉个位。这个循环需要背下来后面很多数字处理题都会用到。循环终止的条件不是“while (n ! 1)”去判断而是“while (true)”加内部返回。因为非快乐数永远不会变成1你要检测的其实是循环是否出现。为什么set能检测循环因为平方和的结果是有限范围内的整数一个n位数的平方和最大是81乘以位数但位数的变化会让结果组合爆炸所以必须记录所有出现过的结果。我个人的体会第一次看到快乐数这题我完全没思路觉得就是模拟计算怎么知道会不会死循环。后来看到题解里用set记录历史结果才明白哈希表不只是用来“查找目标值”还能用来“检测状态是否重复”。这个思想在后来的很多题里都有变体比如环形链表、重复子串问题。4.4 LeetCode 1 两数之和map终于登场题目要求给定一个整数数组和一个目标值找出数组中和为目标值的两个数的下标。解题思路暴力解法是两层for循环O(n²)的复杂度n大了就会超时。哈希优化的思路是遍历数组时对于当前元素nums[i]检查哈希表里是否存在target - nums[i]。如果存在说明找到了答案如果不存在把当前元素的值和下标存入哈希表继续遍历下一个元素。class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int map; for (int i 0; i nums.size(); i) { auto iter map.find(target - nums[i]); if (iter ! map.end()) { return {iter-second, i}; } map.insert(pairint, int(nums[i], i)); } return {}; } };这里有几个很容易想不通的点第一为什么要存“值”作为key下标作为value因为查找的时候我们是根据“target - nums[i]这个值”去搜的所以要拿值做key找到后取出对应的下标。反过来如果存下标做key就无法用值去检索了。第二为什么先查再存还是为了规避同一个元素被用两次。比如target 6数组是[3, 3]如果先把第一个3存进map再遍历第二个3时map里能找到另一个值为3的下标返回正确结果但如果先存再查第一个元素就会找到自己返回[0, 0]显然是错的。所以必须“当前元素不参与当前这一轮的匹配”查完本轮是否匹配再把自己存进去供后面的元素查询。第三返回值是{iter-second, i}顺序是有讲究的先出现的是之前存的元素下标后出现的是当前元素下标。题目只要求返回任意一种顺序的答案但如果你按{i, iter-second}写在某些变体题里就会出错。养成“谁先来谁在前”的习惯会更稳妥。我踩过的坑在用迭代器取value时我一度忘了iter-second和iter-first的区别写反了导致返回的index完全错乱。后来我给自己定了个规矩在map里first是keysecond是value取之前先问自己“谁是查找条件谁是要拿的结果”。5. 常见问题与调试实录5.1 哈希表容器选错set vs map的区别没搞清楚day5四道题里最典型的问题是什么时候用set什么时候用map我刚开始也常混。后来总结了一个判断流程先问自己“我要不要为这个key关联一个附加信息”——如果要比如下标、次数就用map如果不要只要判断存不存在就用set。这个判断流程帮我少走了很多弯路。还有一个容易踩的细节C里set和map都有有序版本set、map底层红黑树和无序版本unordered_set、unordered_map底层哈希表。刷题时绝大多数场景用无序版因为哈希表的优势就是O(1)查找有序版底层是树插入和查找都是O(logn)。如果把这两类搞混复杂度分析就会出现偏差。5.2 边界条件与初始化问题数组模拟哈希时第一要注意的是下标越界。242题里如果字符串包含大写字母或其他字符直接用s[i] - a可能得到负数或超过25的数字数组就会越界。稳妥的写法是先判断字符范围或者把数组长度放大到ASCII全部字符的长度。第二是初始化的坑。C里局部数组int record[26]如果不显式初始化里面的值是未定义的随机值直接用操作会得到不可预期结果。一定写成int record[26] {}或{0}确保每个位置初始为0。这个问题在LeetCode在线环境里不一定会暴露因为编译器可能做了清零但在本地编译就会出现难以排查的随机错误。我建议不管在哪写都养成显式初始化的习惯。第三是输入为空的情况。349题如果nums1为空nums_set就是空set遍历nums2时find永远不会命中结果返回空vector这个逻辑没问题。但242题如果传入空字符串record数组保持全0最后检查也返回true说明空字符串是空字符串的字母异位词这个语义也正确。边界情况一定先在脑子里过一遍再提交代码。5.3 超时的排查看这里day5的题目本身数据规模不大正常情况下不会超时。但如果你的解法写成了暴力O(n²)在极致用例下就会卡时间。遇到超时先看有没有多余的重复遍历再看容器选型是否合理。比如有些同学把349题写成“两层for循环加一个flag数组去重”数据量一大立刻暴露。哈希表的本质就是帮你把第二层for循环省掉把“查找”的时间从O(n)降到O(1)。另外unordered_map的find方法是C11才有的编译器要开对应标准支持。LeetCode默认支持C17本地环境如果用的老版本编译器记得加上-stdc11或更高的编译选项。这个问题看起来小实际上能让一个明明正确的代码在本地疯狂报错。5.4 关于刷题节奏和复盘方式我对照《代码随想录》day5的题单实际操作时给自己定的节奏是先不看题解、不查资料四道题限时90分钟全部写完。这个模式非常推荐因为它会逼你在时间压力下快速做容器选型和边界判断。写完后对照题解复盘重点不是看代码是否和标答一致而是看思路有没有绕远路。复盘时我还会做一件事每道题用另一种语言再写一遍。比如C写完后用Python过一遍用Python的高阶语法巩固思路比如242题用collections.Counter(s) collections.Counter(t)秒杀。这不是炫技而是让你真正理解核心思想而不被具体语言的语法束缚。毕竟面试时可能会用你没那么熟悉的语言手写思路清晰比语法熟练更重要。6. 一些实际体会与后续扩展建议刷完day5这天我自己最明显的感受是哈希表不是背几个API就完事的东西。它背后是“用空间换时间”这一条算法设计原则的具象化。理解了存储的key与value分别代表什么理解了数组、set、map各自适用的范围这四道题才算真正帮助你建立了哈希思维。后续如果你继续按《代码随想录》推进会遇到很多哈希表的变体场景比如三数之和、四数相加、赎金信、最长和谐子序列等等。到那一阶段核心难点不再是哈希表本身而是如何在复杂问题里识别出“需要查找、需要去重、需要关联信息”的环节。day5打下的底子会直接影响你后期做这些综合题的效率。最后分享一个我在实际刷题中沉淀的小习惯每道题通过之后我会在题解末尾写一句“这题用哈希的核心原因”的总结。比如242写的是“字符集有限数组模拟哈希最省”两数之和写的是“查找target-nums[i]时需要返回下标所以用map”。这些短句会在你二刷或面试前快速唤起记忆比重新看一遍完整题解高效很多。这个习惯本来是用来应付遗忘的坚持了几个月之后发现它其实是在帮你把每道题的解题模式沉淀成自己的解题直觉。如果你刚刷到day5别急着往后赶。把242和两数之和这两道题“背”下来不丢人——它们一个代表数组哈希、一个代表map哈希是之后所有哈希题的基石。多写几遍直到不用思考就能写出正确版本再往后推进会轻松很多。