哈希表刷题实战：从底层原理到LeetCode热门题型全解析-北京尧图网络

这期是leetcode刷题记录系列的第八篇我专门把哈希表这一块拎出来写。原因很简单刷题刷到一定量之后你会发现哈希表出现的频率高得离谱两数之和、无重复字符的最长子串、字母异位词分组、和为K的子数组……leetcode热门100题里直接以哈希表为核心考点的就有十几道至于拿它当辅助工具的那就更多了。很多题第一眼看上去像是暴力穷举实际上一换哈希表的思路时间复杂度假装没发生过直接降一个量级。这篇记录我尽量还原自己从“知道哈希表是什么”到“能主动判断什么时候该用哈希表”的完整过程核心内容包括哈希表底层到底是怎么回事、LeetCode里最常见的三类哈希用法、热门100题里的几道典型题目拆解、以及最近一场周赛复盘里踩到的取舍问题。如果你是刚开始刷题或者刷了两三百道还是不太会主动用哈希表这篇文章应该能帮你在思路上打通一道口子。1. 哈希表为什么是刷题绕不开的工具1.1 一眼看懂哈希表在干什么哈希表本质上就是一个“键值映射”的结构Python里最常见的dict和set都是它的实现。键经过一个哈希函数换算成数组下标然后直接定位到存储位置。它解决的核心问题只有一句话把查找从O(n)变成O(1)。举个例子你现在在一个没有序号的班级里找“名字叫小明的人”。如果直接用数组存只能一个个看过去运气差一点100个人要查100次。但如果你有一个“名字转座位号”的对应表无论班里多少人查一次就能定位。这就是哈希表的日常模样它不会改变数据本身只是给你加了一张“快速索引表”。放到算法题里哈希表的存在感其实就是五个字空间换时间。我们额外开一个字典或者集合把遍历过程中遇到的信息记录下来等后面需要的时候不用再回头重新扫描。我经常跟一起刷题的朋友说如果一道题你写出了O(n²)的暴力解且发现内层循环是在“找某个已经出现过的值”那90%的情况可以用哈希表优化到O(n)。1.2 刷题时我们其实只用了哈希表的三成功力说实话大部分刷题攻略讲到哈希表翻来覆去就是三个方法put、get、containsKey。但你要真只拿这三板斧去刷题遇到题型稍微变化就会卡住。哈希表在算法题里真正的价值在于它手里能存的东西很活。不只是存“值”还可以存“下标”“次数”“状态”“组合键”。比如两数之和要在哈希表里存“补数对应的下标”字母异位词分组要在哈希表里存“排序后的字符串对应的数组”和为K的子数组要在哈希表里存“前缀和出现的次数”。这些用法的共同点是你不再需要重复计算只需要查表。所以这篇记录我不打算把每个哈希表的API念一遍那些官方文档写得比我好。我更想说的是哈希表在刷题场景下的判断力什么时候用它、怎么设计键、有哪些底层约束会影响你的代码能不能跑过。2. 不一定看源码但这几个底层原理必须懂2.1 哈希函数与冲突处理关系到你最坏能不能过哈希函数负责把任意的键映射成一个整数下标。理想情况是一个键对应一个位置但现实中不同键映射到同一个位置的情况很常见这叫哈希碰撞。Python的dict用的是开放寻址法碰撞发生后它会往后探测空闲位置有些语言实现用的是链地址法冲突的元素挂成一个链表。你在LeetCode上写Python基本不需要关心这两种方案的区别但有一个知识点面试官很喜欢问哈希表在极端情况下查找会退化到O(n)因为大量数据碰撞后全部落在同一个桶里。正常OJ数据不会故意构造这种情况你也不用过度焦虑但如果代码写上超时了可以考虑是不是哈希函数设计得太差或者你的key本身分布太差。还有一点值得注意整型做key时Python的哈希就是它本身性能最好字符串做key要经过哈希计算元组做key会递归哈希所有元素。所以能选整数key就不要用超长字符串实测在大量数据场景下会有一点点性能差异虽说不至于TLE但养成习惯没坏处。2.2 扩容重哈希与时间复杂度陷阱哈希表的O(1)是平均意义下的。随着插入的数据越来越多哈希表会触发扩容扩容时所有元素要重新计算哈希位置这一次操作是O(n)的。Python的dict会自动处理扩容所以你写代码时无感但如果你的算法极端到在循环里反复重建一个大字典扩容成本会被摊大。我聊这个不是让你去手动预估负载因子而是提醒一个刷题时的成本意识哈希表的空间开销并不小。一个存了10万个元素的Python字典可能占用几十MB内存。有些题看起来能用哈希表秒杀但题目数据范围给到10^5甚至10^6哈希表依然能扛但如果状态空间本身就大比如你要存的key是一个长度100的数组那哈希表很可能直接内存超限这时候就要考虑换思路。2.3 Python里的dict、set、defaultdict、Counter怎么选这里列一个我自己做题时的选型对照表工具适用场景注意事项dict键映射到任意值最常见键必须不可变set只关心“有没有出现过”比dict省一点内存defaultdict(list/int)需要默认值比如分组、计数import collectionsCounter统计可哈希元素的频次本质是dict有most_common方法这个表值得你记一下。很多同学一上来统一用dict然后手动判断键在不在里面、不存在就初始化为0这当然没问题但代码会很啰嗦。用defaultdict或者Counter一行就能解决还少写一个if面试时也会显得更熟练。3. 哈希表在LeetCode里的三类典型用法3.1 查重类set就够了别杀鸡用牛刀第一类最直观判断某个元素在之前是否出现过。最典型的就是“存在重复元素”LeetCode 217更进阶一点的是“无重复字符的最长子串”LeetCode 3里用滑动窗口维护一个不重复区间窗口内字符是否出现过就是用set来查的。这类题的关键点是set的唯一性语义一个元素要么在集合里要么不在没有次数概念。凡是只关心“有没有”的都优先用set而不是dict代码更简洁内存也更省。但要注意如果你还需要知道“出现次数”或者“上次出现的位置”那set就不够用了要升级成dict。3.2 计数类Counter是绝大多数频率题的答案第二类是统计频率。判断两个字符串是不是字母异位词LeetCode 242就是一个标准模板统计s里每个字符的出现次数再统计t里的次数两者相等就是异位词。这种场景用Counter就是两行代码的事。但计数器本身有一个高频面试变体不用额外空间怎么判断异位词。这时候可以用一个长度为26的数组模拟计数器因为字符集是固定的数组本身就是一种更紧凑的“哈希表”。刷题多了你会发现很多所谓的“不用哈希表”解法底层思路还是哈希映射只是实现载体换成了数组。这一点很重要面试时候说“数组其实是一种天然哈希表”会让面试官觉得你不只是背题。3.3 映射类存下标、存状态、存结果是哈希最出彩的地方第三类是映射也是最考验设计能力的一类。哈希表的value不一定是数字可以是你需要反复访问的任何信息。最典型的两个方向值到下标两数之和LeetCode 1里记录每个数的下标补数一到直接返回结果。状态到答案很多DP优化和前缀和题里哈希表保存的是“某个状态出现了多少次”比如和为K的子数组LeetCode 560。这类题的核心在于键的设计。同一个场景键设计得好题目秒解键设计得差可能就是O(n²)。我后面用几道热门题具体展开。4. 从leetcode热门100题看哈希表解题模板4.1 两数之和一道题吃透HashMap的经典思路LeetCode 1“两数之和”是绝大多数人入门哈希表的第一道题。题意很简单找出数组中和为目标值的两个数返回下标。暴力解是两层循环枚举所有数对O(n²)。如果用哈希表只需要一次遍历def twoSum(nums, target): seen {} for i, num in enumerate(nums): diff target - num if diff in seen: return [seen[diff], i] seen[num] i return []这里面有一个很多人第一次没想明白的细节为什么要边遍历边往里存而不是先把全部数据存进哈希表再查第二遍原因很简单为了防止某个元素“自己和自己配对”。比如nums [3, 2, 4], target 6如果先把3 - 0存进去查3的时候直接返回[0, 0]可数组里并没有两个3。边遍历边存当前元素还没入库就不可能出现这种情况同时如果答案存在第二次查的时候一定已经遇到了它的补数。另外有个变体如果题目明确说数组是有序的那这题用双指针从两端往中间夹空间复杂度降为O(1)。这再次说明刷题不是背数据结构而是根据题目条件选工具。4.2 字母异位词分组哈希表配合排序键的教科书式写法LeetCode 49“字母异位词分组”是哈希表设计键的经典题。给一个字符串数组把互为字母异位词的字符串分到同一组。异位词的特点就是字符种类和数量都一样只是顺序不同。所以我们要找一个“归一化”的方式让所有异位词变成相同的键。最直接的方法就是排序两个字符串是异位词当且仅当它们排序后完全相同from collections import defaultdict def groupAnagrams(strs): groups defaultdict(list) for s in strs: key .join(sorted(s)) groups[key].append(s) return list(groups.values())这个解法的复杂度是O(n·k·logk)k是字符串最长长度主要开销在排序。如果字符串很长可以换一种键统计每个字符出现次数组成一个26维的元组让所有异位词共享同一个计数键def groupAnagrams(strs): groups defaultdict(list) for s in strs: cnt [0] * 26 for ch in s: cnt[ord(ch) - ord(a)] 1 groups[tuple(cnt)].append(s) return list(groups.values())这里有一个我踩过的坑必须提醒新手键必须可哈希。Python里list不能做dict的key所以不能用列表当键必须转成tuple。这个错误出现的频率比我预想的高得多尤其是你写代码写嗨了的时候。哪一版更好如果字符串平均长度短排序版本更直观如果长度长但单词数量不多计数元组版本更快。实际面试中两个版本都写一遍能更好地展示你对复杂度的理解。4.3 最长连续序列哈希表不只是一个容器更是一种思维LeetCode 128“最长连续序列”是哈希表题里最容易被小看的一道。题目要求O(n)时间找到最长连续的数字长度比如[100, 4, 200, 1, 3, 2]答案是41、2、3、4。如果用排序复杂度至少O(nlogn)不符合题目要求。哈希表解法是把所有元素放进set然后遍历set只有当当前数字的前一个数不在集合里时才从这个数开始向后数连续串的长度。def longestConsecutive(nums): num_set set(nums) longest 0 for num in num_set: if num - 1 not in num_set: cur num length 1 while cur 1 in num_set: cur 1 length 1 longest max(longest, length) return longest这段代码的精妙之处在于“只看序列起点”。如果一个数前面还有数它就不可能是连续段的开头也就没必要从它开始向后统计。这样就保证了每个数最多被访问两次一次在num - 1 not in num_set判断里一次在while循环里总复杂度仍然是O(n)。我复盘这道题时最深的体会是哈希表的好用之处不是省掉了计算而是让某类判断变成O(1)后你可以放心地做多次判断。这个“多次判断不心疼”的心态才是哈希表能优化暴力解的根本原因。这里有个常见的面试追问能不能在遍历时把已经计入连续段的元素从set里删掉避免重复计数我的答案是可以但你要是真删了得确保while循环的边界处理正确否则容易踩空。实际比赛里我一般不删因为上述写法的复杂度已经达标了再优化属于给自己找事。4.4 和为K的子数组前缀和加哈希表一道题打通两个难点LeetCode 560“和为K的子数组”是哈希表和前缀和结合的最经典题目。给你一个数组求有多少个连续子数组的和等于k。暴力解是枚举所有子数组的起点和终点O(n²)时间复杂度。这题的关键障碍是数组里有负数所以双指针滑动窗口不能用。因为窗口扩大不一定让和变大缩小也不一定让和变小左右指针没法保持单调移动。正确思路先算出前缀和数组prefix[i]表示前i个元素的和。那么子数组[j..i]的和等于k等价于prefix[i] - prefix[j-1] k也就是prefix[j-1] prefix[i] - k。于是我们只需要在一次遍历中维护一个哈希表记录“前缀和的值出现过多少次”from collections import defaultdict def subarraySum(nums, k): count defaultdict(int) count[0] 1 prefix 0 ans 0 for num in nums: prefix num ans count[prefix - k] count[prefix] 1 return ans这个地方有个细节我每次都要跟人强调为什么初始化时要count[0] 1因为前缀和等于0这件事本身表示“从头开始的子数组”如果整个前缀和直接等于k那就需要查prefix - k 0此时map里如果连0都没有就漏掉了从开头计算的子数组。这个初始化是很多人第一次写这道题丢分的地方。另外这题必须“先查再更新count”否则会重复计算以当前元素结尾、长度为0的子数组。代码顺序写反答案会多算。这道题的模板可以迁移到很多看起来和哈希表无关的题比如“连续数组”找0和1个数相等的最长长度、“矩阵区域和”等核心都是前缀和加哈希把区间查询问题转成两值相减问题。5. 从周赛复盘看哈希表的边界感顺便聊聊爱吃香蕉的狒狒5.1 周赛430哈希表不总是最优解最近这几场周赛我都打了430那场做完之后复盘我最大的感受不是哪道题难而是很多人包括我自己早期陷入了一个误区手里有把锤子看什么都像钉子。明明是一道考察排序和贪心的数组题有人第一反应就是开一个哈希表维护区间端点结果把简单问题复杂化代码又长又容易出bug。哈希表本身没有错错的是你在动手之前没有想清楚这道题到底在问什么。哈希表擅长的是“快速找到已经见过的信息”但有些题的信息本来就是有序的排序之后用双指针一次扫描比哈希表更直接有些题问的是“最大值最小化”靠的是二分答案哈希表根本插不上手。我给自己定了个规矩拿到题先看三件事数据是有序的还是无序的需要按顺序访问吗需要多次回头定位吗只有第三个回答是“是”的时候哈希表才应该被优先考虑。这个习惯帮我避免了很多无效代码。5.2 073爱吃香蕉的狒狒别被名字带偏讲到边界感就不得不提LeetCode 073“爱吃香蕉的狒狒”。这题在热搜上一直有讨论但很多刚刷到它的人会误以为这是一道哈希表题狒狒吃香蕉每堆香蕉数量不同是不是得用哈希表统计一下每堆怎么吃实际上这是一道彻头彻尾的二分查找题。题目给出每小时能吃多少根香蕉的速度上限要求找到一个最小速度让狒狒能在警察回来前吃完所有堆。它的特征是结果具有单调性速度越大吃完需要的时间越短。这种“找边界值”的题标准解法是二分答案而不是统计频率或者映射下标。这块给我的启发是刷题不能只看题目描述里的动作词。“吃到”“分配”“组合”这些字眼不代表哈希表真正决定数据结构的是问题需要维护的信息形式。统计次数、查找配对、映射状态才对应哈希表而找极值、找边界、满足单调性大概率对应二分。5.3 一道题该不该用哈希表我列了一张取舍表刷到后面我总结出一张简洁的取舍表每次拿不准的时候就拿出来对一下题目特征首选方向原因需要查找之前出现过的元素哈希表查找O(1)需要统计每个值的次数信息哈希表/Counter键值天然适合需要把“某种状态”映射到答案哈希表状态到结果直接查询数据有单调性、找边界值二分哈希表不提供序关系需要全局有序或者最值排序排序提供分布信息区间内动态维护最值且不要求全局序堆优先队列堆只取极值这张表不是绝对标准但能帮你建立第一反应。等题目刷多了你会发现大部分解法就是“排序、哈希、双指针、二分、堆、动规”这几种思路的组合判断快慢决定你写题的快慢。6. 哈希表刷题避坑手册这些错我替你们踩过了6.1 可变类型不能做key这是Python开发者最容易犯的错误之一。list、dict、set都不能作为字典的key因为它们在哈希之后可能发生变化会导致数据对不上号。遇到需要把数组当成key的场景先转成tuple。我第一次写字母异位词分组时就吃过这个亏代码逻辑完全对一运行就TypeError: unhashable type: list当场愣了三分钟。同理defaultdict里如果用list做key也会扑街。这里有个很好的替代方案如果key的内容是字符串排序后作为key如果是可枚举的数字可以直接用元组。总之先问自己一句这个东西能哈希吗6.2 遍历字典时不要改字典在Python里边遍历字典边往里面加新元素通常会报RuntimeError: dictionary changed size during iteration。这个错误出现得很莫名其妙尤其你在循环里写了个if来更新字典时更容易踩。如果你确实需要在遍历中增量更新建议先收集要加的内容遍历结束再统一处理或者用for key in list(d.keys())的快照方式遍历原始key列表避免迭代器和修改操作互相干扰。这个习惯在刷树和图相关的题目时尤其重要因为递归里经常边搜边记录稍不留神就踩中。6.3 别写又臭又长的get判断用defaultdict很多新手写计数逻辑时是这样的if key in counter: counter[key] 1 else: counter[key] 1这段代码没有问题但完全没有必要。collections.defaultdict(int)两行搞定还更不容易漏初始化。如果你需要返回一个默认值但不想修改字典那就用get(key, default)比如cnt.get(a, 0)。这几个API你写熟之后代码瞬间清爽不少出错概率也低。6.4 空间换时间也有成本上限哈希表的唯一代价是内存。OJ题目一般会给你时间限制和内存限制用哈希表优化时间时心里要有个数数据规模10^5以内随便用10^6要考虑一下存储的是什么东西如果是字符串、对象这类大体积元素可能内存就紧张了。我见过一个比较极端的例子有人把“矩阵中两数之和”的所有组合都存进哈希表去降低时间复杂度结果数据一大内存先爆了。后来改成排序加双指针时间复杂度同样是O(nlogn)空间复杂度却降到了O(1)这提醒我哈希表不是降复杂度的唯一手段更不是免费手段用之前务必评估一下key的数量级。最后再分享一个我自己的习惯这几周刷下来我个人的体会是哈希表是算法题里性价比最高的数据结构它让“用空间换时间”这件事变成了一种条件反射。但真正让我进步的不是背下多少道哈希表题解而是开始在每个暴力解出现的瞬间问自己一句我是不是可以把某一部分信息提前存下来这句话几乎是哈希表题的标准起手式。另外一个很实用的经验是刷题时做“一题多解”。比如两数之和先写暴力再写哈希再想想如果改成有序数组能不能用双指针。一道题用三种解法写一遍比你闷头刷十道同题型印象深刻得多。哈希表类的题目尤其适合这样练因为不同解法的复杂度差异非常明显你能直观感受到每一个优化到底优化了什么。最后吐个槽哈希表系列的题在LeetCode上有个特点看懂答案很容易几行代码思路也简洁但你自己动手写的时候总是会卡在边界条件和键的选择上。这很正常我也卡过很多次。卡住就看一眼看完关掉自己再默写一遍比直接背答案有效得多。哈希表这个知识点本身不难真正难的是把“要不要用哈希表”这个判断内化成肌肉记忆希望这篇记录能帮你少走一点我当时走过的弯路。

哈希表刷题实战：从底层原理到LeetCode热门题型全解析

相关推荐

Tessent Sequential Pattern生成全流程与常见问题排查实战

Raft一致性算法在物联网海量设备管理协调方案中的工程实践

为什么受伤的总是大A：从市场结构到个人风控的完整拆解

更多资讯

Tomcat安装配置全攻略：JDK适配、环境变量与闪退排查

AI应用昇腾迁移实操指南：四层架构与可迁移性评估

SpringBoot+Vue+MyBatis+MySQL宠物上门服务系统解析

存储芯片原理：从电容到晶体管，DRAM与SRAM存储单元深度解析

Coding Agent生产级调优：Harness如何让通过率从30%到70%

MiniMax M Plan 迁移与 H3 视频本地部署：Claude Code 和 Cursor 接入实录

今日更新

基于sEMG与IMU的手语手势识别：从数据采集到实时部署避坑指南

装配车间MES落地指南：SimpleMES工单流转、BOM与齐套检查实战

AI获客怎样减少重复线索？意客AI的原文复用与版本筛选

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？