很多人刷 LeetCode Hot100 的时候都是从哈希这个标签开始的。确实Hot100 里的哈希题分布密集、解法经典而且难度跨度刚刚好既能让你快速建立信心又能把你推向一些比较深的思维角落。这篇文章我就以 Hot100 哈希题为主线把哈希表的应用场景、典型套路、易错点和刷题顺序都拆开聊一遍。内容不绕弯子全部基于我实际刷题和写题解的经验适合刚刚开始刷 Hot100、或者刷了一部分但感觉哈希题老是差点意思的朋友。1. 哈希表到底在刷题中扮演什么角色想弄明白哈希题怎么做得先弄明白哈希表这个数据结构在算法题里到底承担着什么职责。很多人一看到哈希就想到去重、计数这没错但太局限了。哈希表背后真正强大的能力是“快速根据某个键定位到对应的值”这个键可以是一个数、一个字符串、甚至一个元组。在算法题里面我们经常需要“根据某个信息找到另一个信息”这种映射关系用哈希表来存就能把查找时间从 O(n) 降到平均 O(1)。举个例子热题第1题“两数之和”特别能说明问题。题目给一个数组和目标值要求返回两个下标使得这两个数加起来等于目标。最直接的暴力法是双重循环对每个数都去遍历后面的数时间复杂度 O(n²)。但如果你在遍历过程中把一个数已经见过的信息存到哈希表里键是数字的值值是它在数组中的下标那么每次只需要查一下“目标值减当前数”这个键在不在哈希表里就能在 O(1) 时间内确认答案。这一来整个算法的时间复杂度直接降到了 O(n)。这道题虽然简单但它是“用空间换时间”思维的最经典入门。哈希表在热题里另一个常见的作用是“分组”。比如第49题“字母异位词分组”题目要把字母组成相同但顺序不同的字符串放到一起。一个非常直接的想法是能不能把“一组异位词”用一个统一的键来表示当然能。对每个字符串内部的字符排序排序后的字符串就是它的“标准型”。把标准型作为键把所有排序后相同的字符串都挂到这个键下最终字典里的每个值就是一个组。这个方案的核心就是设计一个“键”让它能代表一类元素。除了“查重”和“分组”哈希表还经常配合“前缀和”来统计满足条件的子数组个数。第560题“和为 K 的子数组”就是典型。它需要统计有多少个连续子数组的和等于 K直接枚举所有子数组是 O(n²)如果用哈希表记录“某个前缀和出现的次数”遍历一遍就能算出来。这种情况下哈希表扮演的角色是一个“历史信息记录仪”存的是当前遍历位置之前的状态。所以我的理解是哈希表在刷题中的定位不是某个单一功能而是一种“建立映射、记录状态、加速查找”的通用手段。凡是你觉得“如果在遍历过程中能快速知道以前见过什么就好了”大概率就能用上哈希表。2. Hot100 哈希题里的三板斧遍历哈希、排序哈希、计数哈希我刷完 Hot100 里的哈希题之后发现常用的解题套路其实就三套。第一套是“遍历哈希”核心是在遍历过程中边查边存查的是“之前是否出现过”存的是“当前信息”。第二套是“排序哈希”核心是先把元素变换成一个标准型再用这个标准型做键去分组。第三套是“计数哈希”核心是统计每个元素出现的频次用频次作为键或值来解决问题。这三板斧覆盖了 Hot100 里的大部分哈希题下面我分别结合具体题目详细说。2.1 遍历哈希两数之和与最长连续序列两数之和上面已经提到了我再补充一个容易踩坑的细节必须是“先查再存”而不能“先存再查”。原因是如果数组里有重复元素先存再查可能会把同一个元素当成两个来用。举一个最简单的例子数组[3, 3]目标值是 6正确结果是[0, 1]。如果你先存再查遍历到第二个 3 的时候哈希表里已经有了第一个 3那你查到补数 3 之后返回的可能是[0, 0]这就错了。先查再存的意思是遍历到当前元素时先看看“目标值减当前值”在不在哈希表中如果在说明当前元素和之前某个元素可以组成答案如果不在再把当前元素存入哈希表等后面的元素来匹配它。这个顺序问题几乎是每个人写这道题都踩过的坑。第128题“最长连续序列”是另一道非常典型的哈希题。题目给定一个未排序的整数数组找出数字连续的最长长度。比如[100, 4, 200, 1, 3, 2]最长连续序列是1 2 3 4长度是 4。常规思路是先排序再扫描但排序是 O(n log n)题目要求时间复杂度 O(n)这就需要用到哈希表。做法是先把所有数字放进一个集合然后遍历集合中的每个数字判断这个数字是不是某个连续序列的开头也就是看它的前一个数在不在集合里。如果不在说明它是开头那就从这个数开始不断检查下一个数在不在集合里直到中断。这里容易有个疑问每个数字不都被遍历到了吗为什么是 O(n) 而不是 O(n²)关键在于“只从序列开头开始数”。如果数字 x 的前一个数 x-1 已经在集合里说明 x 不是开头就直接跳过。只有当 x 是开头的那个数才会进入 while 循环去数长度。而每个连续序列只会被数一次且每个数最多只会被后一个数“数到”一次所以整体时间复杂度是 O(n)。这个思路太漂亮了也是“遍历哈希”套路的进阶版本因为它不只是查重而是在用哈希表判断“当前元素是否是某个序列的边界”。2.2 排序哈希字母异位词分组与有效字母异位词第49题“字母异位词分组”是我特别想推荐的一道题因为它能帮你理解“键的设计”到底有多重要。字母异位词的定义是两个字符串包含的字母相同但顺序不同。比如eat和tea就是异位词。我们需要把所有异位词分到同一个组里。最直观的做法是对每个字符串内部排序排序后的结果就可以作为“这一组异位词”的统一标识。为什么排序能作为标识因为异位词的本质是字符组成相同只是排列顺序不同。不管字母的顺序怎么变排完序之后它们都会变成同一个字符串。比如eat排序后是aettea排序后也是aet所以它们会被分到同一个键下。用 Python 写的话代码非常简洁class Solution: def groupAnagrams(self, strs): from collections import defaultdict d defaultdict(list) for s in strs: key .join(sorted(s)) d[key].append(s) return list(d.values())这里有两个特别值得注意的点。第一个是为什么用defaultdict(list)而不是普通 dict。普通 dict 在访问不存在的键时会抛 KeyError你得先判断键是否存在再初始化代码会变长。defaultdict(list)会在访问不存在的键时自动创建一个空列表省掉了setdefault那一步。第二个点是为什么.join(sorted(s))而不是直接sorted(s)作为键。因为键必须是可哈希的而列表在 Python 中是不可哈希的直接拿列表当键会报unhashable type: list。所以需要把排序后的字符列表重新拼成字符串才能当键。这两处细节是我看评论区时发现初学者问得最多的。当然排序法的时间复杂度是 O(n * k log k)其中 k 是最长字符串的长度这在理论上有优化空间。经典的优化方案是用“质数乘积”作为键把 26 个字母分别对应 26 个质数然后计算字符串中每个字母对应质数的乘积。质数乘积相同的字符串其字母组成必然相同因为质因数分解是唯一的。这个方案的时间复杂度为 O(n * k)但要注意整型溢出Python 里无所谓其他语言用长整型也可能溢出。所以我的建议是面试时默认讲排序法如果面试官问“能不能更快”再提一嘴质数法展示你有优化意识。与第49题类似的还有第242题“有效的字母异位词”。这道题只需要判断两个字符串是否为异位词不用分组。最简单的方法还是排序后比较或者用哈希表统计每个字符出现的次数再比较。用 Python 的collections.Counter一行就解决了from collections import Counter class Solution: def isAnagram(self, s: str, t: str) - bool: return Counter(s) Counter(t)Counter本身就是哈希表的子类用起来非常顺手。不过如果你面试时写这行很可能会被追问“如果字符集很大呢”所以最好手写一个用 dict 统计频次的版本思路相同但更能体现基本功。2.3 计数哈希字符频次与键的设计计数哈希的核心是统计频次然后基于频次构建映射。这类题的典型代表是第383题“赎金信”。题目要求判断字符串 ransomNote 能否由 magazine 中的字符构成每个字符只能用一次。做法是用哈希表统计 magazine 中每个字符出现的次数然后遍历 ransomNote每消耗一个字符就减一如果出现负数就返回 False。这类题本质上就是“频次配额”问题。另一个更精彩的计数哈希应用是第76题“最小覆盖子串”。题目要求找到 s 中包含 t 所有字符的最短子串。这里需要用哈希表记录“当前窗口还缺哪些字符、缺多少个”用另一个变量维护“已满足的字符种类数”。当窗口满足条件时尝试收缩左边界寻找更短的子串。这道题是滑动窗口和哈希表结合的极致思路不简单但也正因为如此它的思路可以迁移到很多子串问题里。如果把哈希表的键设计为字符、值设计为“还需要多少个”窗口更新时就是“加一减一”的操作判断条件时就看“是否所有字符的需求量都小于等于零”。计数哈希还有一种常见变体是用“字符计数元组”作为键。比如在某些变位词题目中不排序而是统计每个字符出现次数然后把计数数组转成元组再作为字典的键。比如对abc计数元组可能是(1, 1, 1, 0, ..., 0)。这种做法的好处是不用排序避免了 O(k log k) 的排序开销但需要明确字符集的大小。如果字符集固定且很小比如只有 26 个小写字母用长度 26 的元组当键完全没有问题。LeetCode 第49题如果用这种方法代码会稍微长一点但思路同样清晰。3. 一个绕不开的难点用什么做哈希表的键与值掌握了三板斧后你会发现哈希表题目真正的分水岭不是你会不会用哈希表而是你能不能设计出合适的“键和值”。键决定了一类元素如何被归类值决定了你要记录什么信息。我举几个具体的例子两数之和里键是“数字的值”值是“该数字在数组中的下标”。字母异位词分组里键是“排序后的字符串”值是“属于该组的字符串列表”。和为 K 的子数组里键是“前缀和的大小”值是“这个前缀和出现的次数”。最长连续序列里键是“数字本身”值其实不太重要关键是“集合的存在性”。无重复字符的最长子串里键是“字符”值是“该字符最近一次出现的下标”。我发现一个规律哈希表题的难点很少在“哈希表怎么用”而在“你需要维护什么信息才能让答案在遍历过程中自然浮现”。比如和为 K 的子数组如果你不知道前缀和这个概念就很难想到用哈希表。一旦你想到“两个前缀和之差等于 K”键就自然确定为前缀和。3.1 前缀和 哈希和为 K 的子数组第560题是 Hot100 里很有代表性的一道前缀和哈希题。我们先看代码class Solution: def subarraySum(self, nums, k): from collections import defaultdict d defaultdict(int) d[0] 1 cur 0 count 0 for num in nums: cur num if cur - k in d: count d[cur - k] d[cur] 1 return count这里最关键的两行是d[0] 1和if cur - k in d。为什么初始化时要把前缀和 0 的次数记为 1因为如果某个子数组从数组开头就开始它的和就是cur - 0所以当cur k时我们需要查cur - k 0而0在哈希表中的次数应该是 1才能让这种情况被统计到。如果不初始化d[0] 1当cur k时就会漏掉“从开头到当前”的这个子数组。这个细节特别重要我第一次写的时候就是漏了这个导致示例跑不对。另一个细节是“先查后加”。在每次循环里先判断cur - k是否在哈希表中再把当前前缀和cur加进去。如果先加再查那么在子数组长度为 0 的情况下可能会多算而且当前元素可能被错误地当作子数组的起点导致结果偏大。这个顺序问题虽然小但非常容易错。3.2 字符 哈希无重复字符的最长子串第3题“无重复字符的最长子串”也是哈希表的经典应用。虽然它在 Hot100 里通常被归到滑动窗口类别但它的核心其实是哈希表因为我们需要快速判断一个字符是否在窗口内出现过并知道它上次出现的位置。做法是维护一个左指针 left 和一个哈希表 lastlast 记录每个字符最近一次出现的下标。右指针 right 不断向右走如果当前字符已经出现过且上次出现的位置不在左指针左边就把左指针跳到上次出现位置的下一个位置。标准代码class Solution: def lengthOfLongestSubstring(self, s): last {} left 0 max_len 0 for right, ch in enumerate(s): if ch in last and last[ch] left: left last[ch] 1 last[ch] right max_len max(max_len, right - left 1) return max_len这里last[ch] left这个判断是很多题解里一笔带过、但其实是核心的细节。为什么一定要判断“上次出现位置不小于 left”因为当窗口已经滑动过某个字符时该字符上次出现的位置可能在 left 左边那说明这个字符不在当前窗口内不能把它当作重复字符来处理。如果漏掉这个判断比如字符串abba在处理最后一个a的时候上次a出现在下标 0而 left 已经变成 2 了如果只看ch in last就更新 left会把 left 跳回 1那就不对了。所以必须用last[ch] left确保更新的是窗口内的位置。这是我刷这道题时印象最深的一个坑。3.3 集合 哈希最长连续序列第128题“最长连续序列”用了集合集合本质上也是哈希表只是只存键、不存值。因为题目只需要判断某个数字是否出现过用集合比用字典更契合。这也是一个很重要的思路如果不需要记录值就用集合更简洁、更省空间。代码我在前面已经写过这里我再强调一遍核心逻辑遍历集合中的每个数只对“x-1 不在集合中”的数开始向后数长度。这个判断保证了每个连续序列只被数一次从而让复杂度维持在 O(n)。它充分利用了集合 O(1) 的查找能力是哈希表应用里非常巧妙的一笔。如果你把这道题和“和为 K 的子数组”对比会发现它们虽然看起来差得很远但共性都是“在遍历过程中利用哈希表的 O(1) 查找避免重复计算或重复扫描”。这是我眼中哈希表最重要的价值。4. 从 Hot100 哈希题抽象出的通用解题框架刷题多了之后我开始尝试把哈希题抽象成一个固定的思考框架。拿到一道题先问自己三个问题我需要“根据什么信息”快速找到“什么信息”这个信息能否编码成可哈希的键在遍历过程中键和值如何更新才能保证最终答案自然出现第一个问题决定了哈希表存什么。第二个问题决定了你用什么类型的数据当键比如字符串、整数、元组。第三个问题决定了代码逻辑的顺序比如先查再存还是先存再查、初始化值是多少、边界条件怎么处理。以“字母异位词分组”为例根据“排序后的字符串”快速找到“属于该组的字符串列表”键是字符串值是列表。遍历时每来一个单词就更新一次最终字典收集完所有分组。以“和为 K 的子数组”为例根据“前缀和的值”快速找到“这个前缀和出现了多少次”键是整数值是计数。遍历时先查后更新最终累加答案。这个框架对大多数哈希题都适用也包括一些难题。比如第149题“直线上最多的点”它需要统计经过同一个点的直线上的点数量做法是把“斜率”作为键用哈希表统计相同斜率的点的个数。这又是一个“键的设计”问题你把斜率算出来存成分数或浮点数剩下就是哈希表的基本操作。虽然这题在 Hot100 里不算最热的但解题思路完全统一。还有一个很典型的难题是第380题“常数时间插入、删除和获取随机元素”。它要求所有操作都是 O(1)只用一种数据结构很难满足。常规做法是数组 哈希表数组支持 O(1) 的随机访问哈希表负责存储“元素值到数组下标的映射”。删除时把要删除的元素和数组末尾元素交换再弹出末尾同时更新哈希表这样就能在 O(1) 内完成删除。这里哈希表的作用是“记录位置”属于非常实用但容易被忽略的用法。5. 避坑指南哈希表使用的五个关键细节说了这么多正面思路再集中整理一下哈希表在刷题中常见的坑都是我实际踩过的。第一个坑是键的可哈希性。Python 的 dict 和 set 要求键必须是可哈希的列表、字典、集合都不能当键。如果你想把“字符计数数组”当键必须先转成元组。如果你想把排序后的字符当键必须先.join成字符串。这个错误常见到几乎每篇题解的评论区都会有人问。第二个坑是可变键问题。如果键是可变的哈希值就会变表就乱套了。所以设计键时一定要用不可变类型。这也是为什么很多哈希表题里键都是整数、字符串、元组。第三个坑是先查后存还是先存后查。几乎所有“遍历哈希”类题目都有这个顺序问题。两数之和是先查后存和为 K 的子数组也是先查后更新无重复字符的最长子串是更新后再算长度具体顺序要看题目要求但一定要想清楚不能让当前元素匹配到它自己。第四个坑是初始化值。比如和为 K 的子数组要把d[0] 1提前设置好在统计字符频次时有的题需要初始化所有字符的计数为 0在 LRU 缓存中哈希表初始为空即可。初始化值直接影响了边界条件是否成立。第五个坑是哈希表的时间复杂度不是绝对 O(1)。在最坏情况下哈希冲突严重时可能退化到 O(n)。虽然 Python 对字符串哈希做了随机化处理一般情况下不会遇到恶意碰撞但面试时如果被问到“哈希表最坏复杂度是多少”要能答出 O(n) 以及原因。这个知识在系统设计类题目中也很加分。如果你把上面的坑都避开了Hot100 里的哈希题基本不会有太多编译或逻辑错误。真正困难的还是键的设计和思路的转换那是需要靠题量喂出来的感觉。6. 实操心得我的 Hot100 哈希题刷题顺序与复盘方法文章最后分享一个我实际用的刷题顺序和复盘方法。Hot100 里的哈希题我认为可以按以下顺序刷从易到难每一步都能用到前面学到的思路第一阶段先刷两数之和、有效字母异位词、赎金信这类基础题。这个阶段的目标是熟悉 dict 和 set 的基本操作理解“查重”和“计数”两个基本场景。写完代码后试着把每个方法都改成用普通 dict 而不是defaultdict或Counter实现一遍这样能加深对底层机制的理解。第二阶段刷字母异位词分组、最长连续序列、和为 K 的子数组、无重复字符的最长子串。这个阶段的目标是理解“键的设计”和“遍历过程中如何维护状态”。每道题做完后都问自己一句这里的键是什么为什么选它作为键如果不这么设计还能有其他方案吗把这三个问题想清楚比多刷三道题更有用。第三阶段可以挑战最小覆盖子串、LRU 缓存、常数时间插入删除随机元素。这个阶段的目标是把哈希表和数据结构组合起来用比如哈希表 滑动窗口、哈希表 双向链表、哈希表 数组。这些题目在面试中经常出现并且能体现你的综合能力。如果觉得难可以分两天做第一天看题解理解思路第二天默写代码效果会好很多。关于复盘我自己的习惯是刷完一道题后先提交通过然后去看题解区的高赞答案看看有没有比我的解法更简洁或思路更清晰的做法。如果别人用了不同的键或不同的更新顺序我会在自己的笔记里记下来并把这道题的标签更新为“已掌握”或“需复习”。过两天我会把之前做过的题重新看一遍不看代码只看题目描述尝试在白纸上写出核心思路。如果能一分钟内说出“用什么哈希表、键是什么、怎么更新”这道题就算真正拿下了。哈希表在 Hot100 里其实只是一个起点但把它吃透之后后面很多数组、字符串、滑动窗口、前缀和、甚至设计类题目的路都会好走很多。也许过段时间你再回来看这些哈希题会发现它们已经变成最亲切的一类题了。