Personal Field Archive / Received 2026.09.11
哈希表｜LeetCode 第一轮复盘
从查询目标反推数据结构，复盘集合、键值映射、频率表与特征分组之间的选择边界。
章节状态：第 5 组已完成并复盘。当前已完成 LC 217、1、242、349、205、49。当前主要训练目标不是记住
dict、set或Counter的固定写法，而是根据题目真正需要维护的信息，判断应该使用“存在性集合”“键值映射”“频率表”还是“特征分组”，并理解哈希表如何把反复的线性查找转化为平均O(1)查询。
一、第 5 组题目清单
| 顺序 | LeetCode | 难度 | 题目 | 核心训练 | 当前状态 |
|---|---|---|---|---|---|
| 1 | 217 | 简单 | Contains Duplicate | set、存在性检查、去重 |
已完成 |
| 2 | 1 | 简单 | Two Sum | dict、补数、维护历史信息 |
已复盘 |
| 3 | 242 | 简单 | Valid Anagram | 频率表、Counter、次数比较 |
已复盘 |
| 4 | 349 | 简单 | Intersection of Two Arrays | 集合交集、结果去重 | 已复盘 |
| 5 | 205 | 简单 | Isomorphic Strings | 双向映射、一一对应 | 已复盘 |
| 6 | 49 | 中等 | Group Anagrams | 特征作为 key、分组、tuple | 已复盘 |
二、哈希表的基础心智模型
这一组最重要的变化，是不能再把“哈希表题”理解成“看到题目就创建一个 {}”。真正应该先问的是：
我在遍历过程中，需要保存什么信息？
之后我要根据什么 key 快速查询这些信息？根据需求不同，数据结构也不同。
1. 只关心“出现过没有” → set
例如 LC 217：
当前数字以前出现过吗？需要维护的只有元素本身：
seen = set()典型操作：
if num in seen:
...
seen.add(num)2. 需要“key 对应额外信息” → dict
例如 Two Sum：
数字 → 它之前出现的 index因此需要：
seen[num] = i哈希表不只是告诉我们 num 是否存在，还能立即取回对应的 index。
3. 关心“出现多少次” → 频率表 / Counter
例如 Valid Anagram：
字符 → 出现次数可以手动使用：
counts = {}也可以使用：
Counter(s)Counter 本质上是 Python 已经实现好的“元素 → 出现次数”映射工具。
4. 关心“一一对应关系” → 映射表
例如 Isomorphic Strings：
s 中字符 → t 中字符而且映射必须双向唯一，所以需要同时约束：
s → t
t → s5. 需要“分类” → 特征 key → 一组元素
例如 Group Anagrams：
一个单词的规范化特征 → 所有具有这个特征的单词这里 key 不再是原始元素本身，而是从原始元素计算出的“分类特征”。
这六道题实际上逐渐扩展了哈希表的用途：
217：元素 → 是否出现
1：数字 → index
242：字符 → 次数
349：集合 → 去重与交集
205：字符 → 对应字符
49：特征 → 一组元素三、LC 217. Contains Duplicate
已完成思路
这题只需要判断：
是否存在某个数字至少出现两次。
因此不需要保存次数、index 或其他信息，只需要保存“以前见过哪些数字”。
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False核心认识
如果使用数组反复向后寻找相同数字，就会产生重复遍历；set 把：
这个数字以前出现过吗？转化为平均 O(1) membership 查询。
这题建立了本组最基础的判断：
只关心存在性 / 去重
→ 优先考虑 set重做检查点
- 为什么这里不需要
dict？ set与list做num in ...的平均查询成本有什么差异？- 为什么不需要记录数字出现的具体次数？
四、LC 1. Two Sum
我的初始思路
已经能够把条件：
num1 + num2 = target变形为：
need = target - num也就是说，当遍历到当前数字 num 时，我知道自己还需要什么数字。
最初的问题在于：虽然知道了 need，但想到的是继续遍历数组寻找 need。如果每个数字都向后寻找一次，整体仍然是 O(n²)。
真正的思维转折
不是：
我现在需要 need
→ 去未来的数组中遍历寻找 need而是：
我一路向前遍历
→ 把以前见过的数字保存起来
→ 当前数字计算出 need
→ 查询过去是否已经见过 need例如：
nums = [2, 7, 11, 15]
target = 9
看到 2：
need = 7
过去没有 7
保存 2 → index 0
看到 7：
need = 2
过去有 2
返回 [0, 1]因此哈希表维护的是：
数字 → index正确写法
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i为什么必须先查询，再保存当前数字
对于：
nums = [3, 3]
target = 6第一个 3：
need = 3
seen 中没有 3
保存 3 → 0第二个 3：
need = 3
seen 中已有 3 → 0
返回 [0, 1]这样保证使用的是两个不同位置。
复杂度
遍历数组一次，每次哈希查询和插入平均 O(1)：
时间：O(n)
空间：O(n)本题真正训练的模式
如果我能快速知道“某个东西以前出现过吗”就好了
→ 维护历史信息
→ 用哈希表把未来的查询降为平均 O(1)重做检查点
- 为什么知道
need以后继续遍历仍然是O(n²)？ seen为什么存num → index，而不是只存数字？- 为什么查询必须发生在保存当前数字之前？
- 这题和 LC 217 的共同结构是什么？
五、LC 242. Valid Anagram
我的第一次写法
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
s_letters = set(s)
for letter in t:
if t !in s_letters:
return False
return True这里首先有代码错误：循环变量是 letter，而不是整个 t；Python membership 的否定写法也是 not in。
但更根本的问题是，即使修正成：
if letter not in s_letters:算法仍然不正确。
为什么 set 不够
例如：
s = "aab"
t = "abb"两者的集合都是：
{'a', 'b'}但它们显然不是 anagram：
s：a × 2，b × 1
t：a × 1，b × 2所以题目不是在问：
包含哪些字符？而是在问：
每个字符分别出现多少次？我的修正思路
先为 s 建立频率表：
字符 → 次数再遍历 t，不断把对应次数减一；最后所有值都应该恰好回到 0。
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
s_letters = {}
for l in s:
if l not in s_letters:
s_letters[l] = 0
s_letters[l] += 1
for l in t:
if l not in s_letters:
return False
s_letters[l] -= 1
for count in s_letters.values():
if count != 0:
return False
return TrueCounter 是什么
Python 提供：
from collections import Counter那么：
Counter("aab")大致表示：
{
'a': 2,
'b': 1
}因此：
return Counter(s) == Counter(t)本质上仍然是在比较两个字符频率表。
这一行代码没有改变算法思想，也没有把复杂度变成 O(1)；建立两个 Counter 仍然必须遍历输入，整体为 O(n + m)。
本题真正训练的区别
217：
关心“出现过吗”
→ set
242：
关心“出现多少次”
→ dict / Counter重做检查点
- 为什么
set(s) == set(t)不能判断 anagram？ - 手写
dict时为什么第一次遇到字符不能直接+= 1？ Counter替代的是哪一部分工作？- 一行
Counter(s) == Counter(t)的时间复杂度为什么不是O(1)？
六、LC 349. Intersection of Two Arrays
我的正确写法
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1_col = Counter(nums1)
result = []
for num in nums2:
if num in nums1_col:
if num not in result:
result.append(num)
return result这段代码能够得到正确结果，但数据结构选择还可以更准确。
问题一：不需要 Counter
题目只关心某个数字是否存在于两个数组中，并不关心它出现了几次。
因此：
Counter(nums1)保存的次数信息是多余的，set(nums1) 更贴合题意。
问题二：result 使用 list 会产生线性查询
if num not in result:由于 result 是 list，这个 membership 检查最坏需要遍历整个结果列表。
而题目本身要求结果不重复，因此 set 同时解决：
存在性查询
+
结果去重更合适的写法
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1_set = set(nums1)
result = set()
for num in nums2:
if num in nums1_set:
result.add(num)
return list(result)还可以利用 Python 集合交集：
return list(set(nums1) & set(nums2))本题真正训练的数据结构选择
需要次数
→ Counter
只需要存在性
→ set不能因为 Counter 也能完成 membership 查询，就认为它是最合适的数据结构。应该保存完成任务所需的最小信息。
重做检查点
- 为什么
Counter在这里属于“能用，但信息过量”？ num not in result为什么可能拖高复杂度？- 为什么
set同时满足交集查询和结果去重？ &对两个 set 表示什么？
七、LC 205. Isomorphic Strings
我的初始思路
最初认为需要记录：
字符的位置 + 出现次数例如：
egg：
e 在 index 0，出现 1 次
g 在 index 1、2，出现 2 次
add：
a 在 index 0，出现 1 次
d 在 index 1、2，出现 2 次这个描述能够观察到 isomorphic 的外在模式，但落实到代码会很复杂，因为它没有抓住真正需要保持的不变量。
真正的判定条件
Isomorphic 要求：
s中同一个字符每次都必须映射到t中同一个字符，并且两个不同字符不能映射到t中同一个字符。
对于：
egg
add真正需要维护的是：
e → a
g → d第三个位置再次看到 g → d，与原映射一致，因此合法。
对于：
foo
bar会出现：
f → b
o → a
o → r ← 与原来的 o → a 冲突因此 False。
为什么单向映射还不够
考虑：
s = "ab"
t = "cc"如果只维护：
a → c
b → c每个 s 字符自身都没有发生“一个字符映射到两个字符”的冲突，但两个不同字符映射到了同一个 c，仍然不合法。
所以需要双向唯一：
s → t
t → s正确写法
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
s_to_t = {}
t_to_s = {}
for a, b in zip(s, t):
if a in s_to_t and s_to_t[a] != b:
return False
if b in t_to_s and t_to_s[b] != a:
return False
s_to_t[a] = b
t_to_s[b] = a
return True本题真正训练的模式
哈希表不只是保存“有没有”或“多少次”，也可以维护约束关系：
key → 与它对应的 value205 的关键是不去记录所有 index，而是在遍历对应位置时直接检查映射是否始终一致。
重做检查点
- 为什么“位置 + 次数”能描述现象，却不是最简洁的不变量？
- 为什么
s_to_t单向映射不足？ ab与cc为什么可以击穿单向映射？- 两张哈希表分别防止哪一种映射冲突？
八、LC 49. Group Anagrams
从 LC 242 推导到 LC 49
242 的问题是：
两个字符串的字符频率是否相同？49 则把问题扩大为：
如何把一组互为 anagram 的字符串自动归到同一组？关键变化不是不断拿两个单词互相比较，而是：
能不能为每个单词计算一个规范化特征，使所有 anagram 得到完全相同的 key？
于是问题变成：
word
↓
计算分类特征 key
↓
groups[key].append(word)方法一：排序后的字符串作为 key
例如：
eat → aet
tea → aet
ate → aet
tan → ant
nat → ant
bat → abt所有 anagram 排序后都会变成相同字符串，因此可以：
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = {}
for word in strs:
key = ''.join(sorted(word))
if key not in groups:
groups[key] = []
groups[key].append(word)
return list(groups.values())方法二：26 个字母的频率作为 key
对于只包含小写英文字母的字符串，可以建立：
count = [0] * 26每个位置对应一个字母：
index 0 → a
index 1 → b
...
index 25 → z通过：
count[ord(c) - ord('a')] += 1统计字符频率。
那么 eat、tea、ate 最终得到完全相同的 26 个计数。
为什么需要 tuple(count)
list 是可变对象，不能直接作为 dict 的 key：
groups[count] # 不可行因此转换成不可变、可哈希的 tuple：
key = tuple(count)完整写法：
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = {}
for word in strs:
count = [0] * 26
for c in word:
count[ord(c) - ord('a')] += 1
key = tuple(count)
if key not in groups:
groups[key] = []
groups[key].append(word)
return list(groups.values())tuple 在这里做了什么
它没有改变 26 个计数代表的内容，而是把：
[1, 0, 0, ..., 1, ..., 1]转换成：
(1, 0, 0, ..., 1, ..., 1)后者不可变，因此能够被哈希并作为字典 key。
两种方法的复杂度
假设有 n 个字符串，每个字符串平均长度为 k。
排序法对每个字符串排序：
O(k log k)总时间约：
O(n · k log k)字符计数法只遍历每个字符串一次：
O(k)总时间约：
O(n · k)26 个计数是固定大小，因此不会随字符串长度增长。
本题真正训练的新模式
49 第一次非常明确地训练：
不是查询一个现成的 key
而是先从对象中计算出“分类特征”
再用这个特征作为 hash key即：
特征 key → 属于这一类的所有元素重做检查点
- 为什么不应该对所有字符串两两调用 Anagram 判断？
- 什么性质使一个特征能够作为正确的分组 key？
- 为什么排序后的字符串可以作为 key？
- 为什么 26 个字符频率也可以作为 key？
- 为什么
list不能作为 dict key，而tuple可以？ groups.values()为什么正好是题目要求返回的内容？
九、当前形成的哈希表统一思维
1. 先问“我需要查询什么”，再决定数据结构
不要看到题目属于“哈希表组”就机械创建 dict。
应该先区分：
只需要知道存在性？
→ set
需要 key 对应额外信息？
→ dict
需要统计次数？
→ dict / Counter
需要维护对应关系？
→ dict
需要按特征分类？
→ dict[key] = group2. 哈希表常用来保存“过去的信息”
Two Sum 是这一点最典型的例子：
当前元素
→ 根据当前元素计算需要查询的东西
→ 到哈希表中查询过去已经维护的信息这种结构能够避免针对每个当前元素再次遍历过去或未来的数据。
3. key 不一定是原始数据
217 中 key 就是数字本身；205 中 key 是字符；但 49 中 key 是经过计算得到的“规范化特征”。
因此遇到分类问题时应该问：
有没有一种表示，使属于同一类的对象一定得到相同表示？
4. “存在”“次数”“位置”“映射”是不同的信息需求
这几道题最容易混淆的地方，是不同容器看起来都“能做”。
例如 Counter 也可以用于 349，但题目不需要次数；dict 也能模拟 set，但 217 不需要 value。
选择数据结构时应该尽量让其语义和问题一致：
217：存在
1：位置
242：次数
349：存在 + 去重
205：映射
49：分类5. 哈希表是在用空间换查询时间
Two Sum 从暴力的 O(n²) 下降到平均 O(n)，代价是额外维护最多 O(n) 大小的哈希表。
因此“哈希表更快”不是没有成本，而是：
增加额外空间
→ 保存未来可能需要的信息
→ 避免重复线性查找6. Python API 不能替代算法理解
Counter(s) == Counter(t)虽然只有一行，但仍然是在建立并比较两个频率表。
set(nums1) & set(nums2)虽然只有一行，但仍然是在建立两个集合并求交集。
因此复盘时不能只记 API，而应该能够解释它们背后的数据结构和复杂度。
十、当前暴露出的共性问题
1. 已经能想到“我要找什么”，但还需要进一步想到“提前维护什么”
Two Sum 中已经自然得到：
need = target - num但第一反应仍然是遍历寻找 need。下一阶段需要形成：
如果我要反复查某个东西
→ 能不能在遍历过程中提前维护一个哈希结构？2. 容易把“存在性”与“频率”混在一起
242 第一次使用 set，说明需要进一步区分：
集合相同
≠
每个元素出现次数相同aab 与 abb 是最重要的反例。
3. 数据结构虽然能完成任务，但未必最贴合题意
349 使用 Counter 可以工作，但不需要频率信息；result 使用 list 又让去重检查变成线性查询。
因此不能只问：
这个数据结构能不能做？还要问：
它是否保存了多余信息？
它的关键操作复杂度是否符合我的目标？4. 需要从“观察外在模式”进一步提炼“不变量”
205 中“位置 + 次数”确实观察到了 egg 与 add 的结构，但代码难以落实。真正的不变量是：
同一个字符始终映射到同一个字符
不同字符不能映射到同一个字符算法设计时，应尽量寻找能够在每一步直接检查的不变量，而不是记录所有表面现象。
5. 需要逐渐掌握“设计 key”
49 是本组最重要的升级之一。此前的 key 基本来自原始元素本身；49 要主动构造：
排序结果
或
字符频率 tuple作为 key。
这意味着哈希表题进一步从“会使用 dict”进入：
如何找到能够代表问题状态或分类的正确 key？
十一、哈希表题统一检查清单
- 题目真正需要的是“存在”“次数”“位置”“映射”还是“分类”？
- 我是否正在对同一批数据反复做线性查找？能否提前维护哈希表？
- 如果只关心存在性，是否应该使用
set而不是dict/Counter？ - 如果需要额外信息，
dict的 key 和 value 分别应该表示什么？ - 如果需要频率，是否应该维护
元素 → 次数？ - 当前哈希表保存的是“过去的信息”还是“分类结果”？每次遍历如何更新？
- 如果题目要求一一映射，是否只检查了一个方向？反方向是否也必须唯一？
- 如果题目要求分组，我能否为每个对象计算一个稳定的规范化 key？
- 两个逻辑上同类的对象是否一定产生相同 key？不同类对象是否可能错误地产生相同 key？
- 这个 key 是否可哈希？如果使用 list，是否需要转换成 tuple？
- 是否在结果 list 上做了
x in result之类的线性查询，从而破坏整体复杂度？ - 使用
Counter、集合运算等 Python API 时，我是否仍然能解释其底层逻辑和复杂度？ - 当前优化是否用额外
O(n)空间换取了平均O(1)查询？这个 trade-off 是什么？ - 能否给出一个反例，证明更简单的数据结构为什么不够？
十二、延迟重做安排
在 3～7 天后从空白重做：
217、1、242、349、205、49完成标准不只是通过测试，还应能够说明：
- 为什么这题适合哈希表；
- 为什么选择
set、dict、Counter中的某一种； - key 和 value 分别代表什么；
- 哈希表在遍历过程中维护了什么状态；
- 为什么能够避免原本的重复遍历；
- 时间复杂度和空间复杂度分别是什么；
- 是否存在更简单但错误的数据结构选择，并能给出反例；
- 如果是分组题，为什么设计出的 key 能稳定代表一个类别。
如果能够在不参考答案的情况下重做这六题，并能从“存在性、频率、位置、映射、分类特征”五种信息需求出发独立选择数据结构，可以将第 5 组基础哈希表部分标记为稳定掌握。