哈希表

一句话：哈希表把”这个东西之前见过吗/出现过几次/对应什么”这类查询降到 O(1)。凡是暴力解法里有一层”遍历前面所有元素，看有没有满足条件的”，几乎都能用哈希表把那层遍历换成一次查表。

用哈希表换掉暴力里的第二层循环

01-两数之和 是最典型的例子：暴力解是两层循环枚举所有 pair，O(n²)；优化思路是边遍历边把”见过的数 → 下标”存进哈希表，对每个新数只需要查一次”目标值减它，之前见过吗”，把第二层循环变成 O(1) 查表。这个模式几乎可以套用到所有”找一对/一组满足某种关系的元素”的题目上。

49-字母异位词分组 是同一个思路的分组版：把每个字符串映射成一个能代表其字符组成的”规范键”（排序后的字符串，或者 26 个字母的计数元组），键相同的字符串必然是字母异位词，用哈希表把键相同的分到同一组，一次遍历完成分组。

128-最长连续序列 要求 O(n) 而不是排序的 O(n log n)：把所有数丢进哈希集合后，只对”是某个连续序列起点”的数（即 num-1 不在集合里）才往后扩展计数——这一个判断把总的扩展次数从 O(n²) 摊薄回 O(n)，是摊还分析的经典案例，详见摊还。

560-和为K的子数组 把哈希表和前缀和组合在一起（见数组与字符串）——哈希表存的不是”元素”而是”前缀和出现的次数”，同一个”查表代替遍历”的思想，换了个查询对象。

哈希表 + 结构：O(1) 的容器设计题

这批题不是”用一次哈希表查询”，而是设计一个内部靠哈希表 + 别的结构组合、支持 O(1) 增删查改的容器：

• 146-LRU缓存：哈希表（O(1) 定位节点）+ 双向链表（O(1) 调整访问顺序）。哈希表负责”这个 key 对应哪个节点”，链表负责”谁是最近最少使用的”——单独一个结构都做不到两件事都是 O(1)，组合起来才行。
• 460-LFU缓存：比 LRU 多一维”频次”，需要哈希表 + 哈希表（key→节点、频次→该频次的节点双向链表），外加一个”当前最小频次”的游标，三者配合才能在 O(1) 内完成淘汰。
• 380/381-O(1)时间插入删除随机：哈希表存 值→数组下标，删除时把待删元素和数组最后一个元素交换再弹出，避免了数组中间删除的 O(n) 搬移——哈希表在这里的作用是让”数组中间删除”降级成”数组末尾删除”。
• 432-全O(1)的数据结构：LFU 的进一步抽象，同样是”哈希表定位 + 双向链表维护顺序”的组合。

这批题的共同教训：单一数据结构往往只能保证”某一个操作是 O(1)“，把哈希表和另一个能表达顺序/结构的容器（链表、数组）拼在一起，才能让所有操作同时是 O(1)——哈希表贡献的永远是”定位”，另一个结构贡献”顺序”或”物理布局”。