从零整理哈希表专题几道让我反复回看的LeetCode题目与踩坑记录这是我的leetcode刷题记录系列第8篇这次集中把哈希表相关题目过了一遍。坦白说哈希表这个专题并不算难真正难的是“什么时候该用哈希表、什么时候不该用”。很多题表面上说用哈希表实际卡人的点全在边界处理和时空平衡上。这篇文章我把近期做的哈希表题目挑几道典型的展开说包含完整思路、代码和复盘也把我在这个专题里踩过的坑列出来希望能给正在刷题的读者一些参考。1. 哈希表专题的底层认知它到底解决什么问题1.1 哈希表的核心价值用空间换时间哈希表在日常生活中最好理解的一个类比就是“通讯录”。你不需要从头到尾翻一遍几百个人的名单才能找到张三你只需要知道姓氏拼音直接翻到对应那一页就行。底层逻辑是通过一个哈希函数把key映射到固定的存储位置查找、插入、删除平均时间复杂度是O(1)。在刷题层面哈希表基本解决两类问题存在性查询和唯一性映射。存在性查询就是“这个元素之前见没见过”比如两数之和里我要判断target - nums[i]是否出现过唯一性映射就是“把某类东西归到同一组”比如字母异位词分组里把排序后的字符串作为key。这两类问题在LeetCode上出现的频率极高。热门100题里面哈希表直接作为解题核心的题目少说也有七八道间接用到的那就更多了。刷完这个专题我的一个体会是哈希表本身不难写难的是判断什么时候用unordered_map、什么时候用数组、什么时候两种都行但要考虑数据范围。1.2 哈希表在刷题中的通用解题框架经过这些题目我总结出一个比较通用的思考顺序分享给大家参考第一步判断题目是否涉及查询历史元素、统计频率、建立映射关系第二步看数据范围和元素类型决定用数组模拟哈希表还是标准库哈希表第三步想清楚哈希表的key和value分别存什么——这一步最容易被忽略很多题做不出来或者代码写出来很乱就是因为没想清楚value的语义第四步考虑是否有顺序要求如果有哈希表配合遍历顺序信息会有什么影响。举个例子如果题目中元素的范围很小比如字符串s只包含小写字母用int[26]数组反而比unordered_map更高效因为数组避免了对哈希函数和冲突处理的额外开销。但如果key的范围很大或者不连续比如字符串、长整数数组就不现实了这时必须用哈希表。注意面试或者笔试中如果key是字符且范围明确优先用数组而不是unordered_map。这不只是性能问题——我自己在面试中曾因为用了unordered_map而被迫多解释一句哈希冲突但用数组的话完全不需要。1.3 为什么这个专题值得单独刷一遍我记得自己在早期刷题时有个误区哈希表的题“看一眼就知道答案”于是跳着刷结果遇到变体题就卡住。后来发现哈希表专题的题虽然方法相对统一但它和其他专题的衔接非常紧密——双指针、滑动窗口、前缀和、甚至图论的建图过程都会用到哈希表。把哈希表专题单独刷一遍其实是在训练一个“映射思维”你能不能把一个复杂问题转化为key-value关系能不能想到用额外存储结构来简化问题。这种思维在其他专题里起到的是乘法效果所以我建议读者即使时间紧张也值得把这个专题完整过一遍。2. 热门100题中的哈希表题目实战拆解2.1 两数之和哈希表入门的“Hello World”题目很经典给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值的那两个整数并返回它们的数组下标。这道题的暴力解法是双重循环时间复杂度O(n^2)。优化的核心思路是当我遍历到nums[i]时我需要知道target - nums[i]是否在之前出现过并且要拿到它的下标。这正好是哈希表的“存在性查询”“唯一性映射”的典型场景所以用unordered_map存储“元素值 - 下标”。这里我想强调一个细节为什么只遍历一遍就够了因为当遍历到nums[i]时如果哈希表里已经有target - nums[i]那我们找到了答案如果没有就把nums[i]插入哈希表继续往后走。之后如果遍历到nums[j] target - nums[i]那么它一定能在哈希表里查到nums[i]。换句话说两个数中无论谁先被遍历到都能在对方出现时被发现所以一遍遍历就足够。class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int hash; for (int i 0; i nums.size(); i) { int need target - nums[i]; if (hash.count(need)) { return {hash[need], i}; } hash[nums[i]] i; } return {}; } };时间O(n)空间O(n)这个解法的核心思想就是“用空间换时间”的经典代表。从这道题开始我养成了一个习惯遍历过程中只将已经处理过的元素放入哈希表而不是预处理全部放入。这个区别在后续很多题目里都有体现比如和为K的子数组如果预处理全部元素而不是在遍历时动态更新前缀和频率的统计就会出错。2.2 最长连续序列哈希去重后如何设计查询方向给定一个未排序的整数数组nums找出数字连续的最长序列不要求序列元素在原数组中连续的长度。这道题在热门100题里也有一席之地。乍一看这道题像是在考排序双指针但用哈希表可以做而且更加巧妙。核心思路是把所有元素放入set去重然后遍历每一个元素如果x - 1不存在即x是一个连续序列的起点就从x开始向后枚举x1、x2……统计连续长度。为什么只从“起点”开始枚举这是这道题的关键。如果当前元素x存在前驱x-1那么从x开始枚举得到的连续序列一定是从x-1开始枚举得到的连续序列的子集属于重复计算。所以只对“没有前驱”的元素开始枚举每个元素在最坏情况下至多被访问两次一次判断是否存在一次作为某个序列的成员被枚举整体时间复杂度是O(n)。class Solution { public: int longestConsecutive(vectorint nums) { unordered_setint s(nums.begin(), nums.end()); int ans 0; for (int x : s) { if (s.count(x - 1)) continue; int cur x; int len 1; while (s.count(cur 1)) { cur; len; } ans max(ans, len); } return ans; } };这道题我实际写过一遍之后发现了一个小坑遍历unordered_set时不能在循环体里修改容器本身插入/删除否则迭代器会失效。但这种只读操作的场景完全没问题。另外把vector直接构造为unordered_set时底层会做一次全量插入代价是O(n)后续所有查询就是O(1)了。还有一个小知识点如果题目要求返回最长序列的长度而不是具体序列那只用set就够了如果要返回具体序列的起止值那在枚举过程中需要额外维护区间端点。不过LeetCode这道题只需要长度所以代码可以保持简洁。2.3 和为K的子数组前缀和配合哈希表的经典范例这道题可以说是哈希表和前缀和结合的教科书题目给定一个整数数组和一个整数k你需要找到该数组中和为k的连续子数组的个数。如果只用暴力枚举起点和终点复杂度O(n^2)。优化的思路是子数组的和可以表示为前缀和的差值——即子数组[i, j]的和等于preSum[j] - preSum[i-1]。那么“和为K”就等价于“preSum[j] - preSum[i-1] K”也就是说当我们遍历到第j个位置时我们需要知道在之前的位置里有多少个前缀和等于preSum[j] - K。于是这里哈希表的value语义变成了“某个前缀和出现的次数”。这是我在这道题里最大的收获哈希表的value不一定非要是下标或者元素本身根据题目需求频率计数是最常见的value形式。class Solution { public: int subarraySum(vectorint nums, int k) { unordered_mapint, int hash; hash[0] 1; // 前缀和为0出现一次代表空数组 int preSum 0; int ans 0; for (int num : nums) { preSum num; if (hash.count(preSum - k)) { ans hash[preSum - k]; } hash[preSum]; } return ans; } };这里有一个非常关键的细节hash[0] 1这个初始化不能丢。如果不初始化那么当preSum恰好等于K时preSum - K 0我们需要从曾经出现过的前缀和里寻找0而0这个“空前缀”从未被记录过就会漏算从数组开头到当前位置的整个子数组。我在第一次写这道题时就是漏了这一步结果测试用例[1, 1, 1]k2时正确答案是2我输出1排查了很久才发现是初始化问题。这个细节值得每个刷题的人特别留意。再说一点扩展如果题目改成“和不大于K的最长子数组长度”保证元素非负前缀和配合双指针会更好用因为此时我们可以在前缀和数组上做双指针滑动窗口空间降到O(1)。这说明刷题时“同一场景要看具体条件再选工具”不能无脑哈希表。2.4 字母异位词分组哈希表在分组问题中的典型应用给你一个字符串数组请你将字母异位词组合在一起。字母异位词指的是由相同字母重排列形成的单词包括相同字符串。这道题的思路非常直接异位词排序后得到的字符串完全相同把排序后的字符串作为key原字符串列表作为value一遍遍历即可完成分组。class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring hash; for (string s : strs) { string key s; sort(key.begin(), key.end()); hash[key].push_back(s); } vectorvectorstring ans; for (auto [k, v] : hash) { ans.push_back(v); } return ans; } };这道题表面上平平无奇但它引出了一个性能优化视角如果字符串很长对每个字符串都做O(k log k)的排序总代价不低。替代方案是用长度26的计数数组生成一个“签名”比如[1, 0, 1, 0, ...]转成字符串做key贪心地把排序变成线性。不过这只是降低了常数时间复杂度仍然受限于字符串总长度。我个人在笔试中见过这道题的变体给定一个字符串数组要求按字母异位词分组但同时要求分组内按字典序输出。这种情况下其实排序后分组依然好使但要注意对每个分组内部再排序一次或者在对原字符串排序时同时保留原串和排序串这样代码逻辑会稍微复杂一点。这类小改动很能体现代码组织的功底建议读者自己动手写一遍。3. 看似哈希表的题有时不是哈希表爱吃香蕉的狒狒复盘3.1 为什么这道题容易产生误解在相关热词里看到了“073爱吃香蕉的狒狒”这道题正好是我最近做过的。这道题题名里没有“哈希表”但很多人会觉得“狒狒吃香蕉”这种题应该用哈希表记录每堆香蕉数量实际上完全不是。如果你这样想就直接钻进了题目陷阱里。题目大意是狒狒有N堆香蕉每堆有piles[i]根她每小时可以选择一堆香蕉吃掉K根如果该堆少于K根就全部吃掉这一小时内不会再吃其他堆要求在所有香蕉被吃完之前守卫回来求最小的K。这道题的核心是“在给定速度K下计算总耗时”然后对K进行二分搜索。目标函数是单调的K越大耗时越短。所以本质是二分答案不是哈希表。3.2 二分查找的边界与check函数的写法check函数是核心给定速度K计算吃完所有香蕉需要多少小时。每一堆耗时是piles[i] / K向上取整long long hours 0; for (int p : piles) { hours (p K - 1) / K; }上取整的写法(p K - 1) / K是整数运算里的常用技巧建议直接背下来避免用浮点数产生精度问题。二分边界左边界是1最小速度不能小于1右边界是max(piles)速度为最大堆数量时每一堆恰好1小时总耗时 堆数。二分查找最小的K使得总耗时不超过H。class Solution { public: int minEatingSpeed(vectorint piles, int h) { int left 1; int right *max_element(piles.begin(), piles.end()); while (left right) { int mid left (right - left) / 2; long long hours 0; for (int p : piles) { hours (p mid - 1) / mid; } if (hours h) { right mid; } else { left mid 1; } } return left; } };这道题让我印象最深刻的一点是当你把“用哈希表”当成一种惯性时很容易把一个二分答案题和哈希表关联起来因为你误以为需要统计频率。其实复杂度的来源不是去重或者统计而是最优化问题的判定性质。这也提醒我拿到题先想“这题的性质是什么”再想“用什么数据结构”。注意如果题目直接给出了目标值H并且速度函数是单调的十有八九是二分答案。哈希表在这个模式下最多是辅助记录而已不应该成为主解法。3.3 省流总结哪些场景才真正需要哈希表经过大量题目我给自己整理了一个快速判断准则需要在O(1)时间内判断“元素是否出现过” - 哈希表是首选需要统计出现次数或频率 - 哈希表或计数数组需要把同类元素归组 - 哈希表做key映射存在一个单调函数并求最优值 - 优先想二分不要被题目场景迷惑对顺序有强依赖 - 考虑滑动窗口、双指针、前缀和哈希表只是辅助。这个准则在周赛430等近期的比赛中也反复得到验证。做这些新题时很多题目表面考察“双指针”或者“区间问题”但总是需要哈希表去辅助维护窗口内的状态。如果你对哈希表使用场景不敏感往往会把简单问题做复杂。4. 哈希表使用的技术细节与避坑经验4.1 unordered_map的底层行为与性能陷阱C标准库的unordered_map底层是哈希表它和map红黑树最大的区别是map的key是有序的unordered_map不是map的插入/查找是O(log n)unordered_map平均是O(1)。刷题优先用unordered_map而非map因为大多数题目不需要有序性而unordered_map常数更小。不过unordered_map并非没有坑。最典型的问题就是哈希冲突。当大量key发生碰撞时查询退化成O(n)不过刷题很少遇到刻意构造的卡哈希数据。标准库实现里当bucket数量不够时rehash会重新分配所有桶这是一个相对昂贵的操作。如果在刷题时遇到大量插入的场景可以调用reserve来预留容量减少rehash次数。unordered_mapint, int hash; hash.reserve(nums.size()); // 提前预留足够空间 hash.max_load_factor(0.7); // 控制负载因子减少冲突坦白说我之前很少关注这两行直到有一次做了一道需要频繁插入查询的题用默认unordered_map比预分配的慢了一半左右。虽然LeetCode不卡常数但在面试中如果你能说出这两行的作用会是加分项。4.2 遍历中修改容器是大坑迭代器失效问题unordered_map和unordered_set在遍历时如果插入了新元素导致rehash所有迭代器都失效。如果你在遍历循环里对同一容器做插入或删除很容易产生未定义行为。我在做一道题时踩过这个坑想遍历哈希表并删除满足条件的元素直接写了hash.erase(it)后继续使用it结果运行OK但结果错乱调试了很久才发现是迭代器失效导致。正确的删除方式是for (auto it hash.begin(); it ! hash.end();) { if (需要删除) { it hash.erase(it); // erase返回下一个有效的迭代器 } else { it; } }这个经验在刷题阶段不一定每天用到但一旦用到就是大坑。建议读者把这段代码记在笔记里以备不时之需。4.3 自定义key与std::hash如果需要用pair、tuple、vector等容器作为keyC标准库不会默认提供hash特化直接编译报错。常见的解决方案是把pair转成一个long long比如左移32位后再或上第二个数或者转为字符串作为key。在刷题时最省事的方案是转为字符串因为写起来直观但性能上字符串哈希多了一层开销。其实更高效的方案是自定义hash结构体。比如struct PairHash { size_t operator()(const pairint, int p) const { return hashlong long()( ((long long)p.first 32) ^ p.second ); } }; unordered_setpairint, int, PairHash s;如果你的代码要处理二维坐标点、状态二元组这类key自定义hash很有用。不过对LeetCode而言除非你对格式很有把握否则我建议优先用“编码成long long”的方式这样不需要自定义hash也不太容易出错。4.4 关于count、find和[]选择的心得在unordered_map上判断key是否存在有三种常见写法count、find、直接operator[]。很多刚刷题的同学习惯直接写hash[key]但如果key不存在[]会默认插入一个value为0的键值对这在“存在性判断”的场景中会产生副作用也可能会把整个map撑大影响性能。我的习惯是判断存在性用count需要同时取出并判断用find需要修改value时再用[]。这个习惯帮我避免了好几类隐蔽bug尤其在做“频率计数”类题目时如果不小心用[]先建了一个无效key之后对这个key的count判断就会出错。5. 关于哈希表刷题路线的建议如果这篇博客能对你有一点帮助那么我最想传递的是刷这个专题不要贪多贪快。我自己的刷题节奏是每天3~5道每道题在AC之后再多想两个问题如果数据范围扩大10倍解法还成立吗如果题目改一个条件思路会怎么变哈希表专题和二分、前缀和、滑动窗口结合得非常紧密所以推荐刷完这个专题后紧接着刷前缀和、滑动窗口的专项题会感觉许多题目触类旁通。最近我也开始关注周赛的题目周赛430中就出现了和哈希表场景相关的题目核心考点其实是“如何用哈希表维护窗口状态”。如果你能在日常训练中真的想清楚每一道题的底层逻辑而不是背模板周赛中遇到类似考点会轻松很多。最后再分享一个小技巧我在刷哈希表题时习惯把每道题的“key的语义”“value的语义”单独写在一行注释里这样回头复习时一眼就能看出这道题的映射本质。比如说两数之和注释写// key: 元素值, value: 下标和为K的子数组注释写// key: 前缀和, value: 出现次数。这个习惯帮我在面对变体题时快速建模也算是我这段时间刷哈希表最大的收获之一。