哈希表解题框架
本节目标
用集合或映射消除重复查询，把配对、分组和连续性问题转化为近似常数时间的查找。
哈希表适合解决一类共同问题：算法不断询问“某个信息以前是否出现过”，而答案不依赖这些信息的有序关系。它不是为了替代所有遍历，而是为了消除遍历中的重复查询。
识别信号
遇到下面的题面特征，可以先考虑能否用哈希表维护已经处理过的信息：
- 反复判断某个值、字符或状态是否出现；
- 统计元素出现次数，或按某个特征把元素分组；
- 为当前元素寻找一个与它配对的历史元素；
- 只关心存在性、次数或关联信息，不需要最小值、排名等有序信息。
哈希表最重要的识别信号不是“数组中有数字”，而是暴力算法把大量时间花在重复查找上。
问题模型
设我们从左到右处理输入。朴素做法常在每个位置重新扫描已经处理过的部分，询问“目标信息在不在”。如果一次扫描需要线性时间，外层再遍历一次，总复杂度就可能达到平方级。
把已经见过的信息记录到哈希表后，查询、插入和更新的期望时间通常为均摊常数级。于是整体过程可以整理为：
- 从当前元素推导本轮要查询的键；
- 在历史状态中查询这个键；
- 根据查询结果更新答案；
- 把当前元素提供的信息写回状态。
集合与映射
- 集合（set） 只记录键是否存在，适合去重、成员判断和连续性检测。
- 映射（map） 记录“键 → 附加信息”，适合保存次数、下标、分组结果或最后出现位置。
选择依据是查询后还需要什么：只要知道“见过”就用集合；还要取回下标或计数就用映射。不要为了熟悉某个容器而保存用不到的数据。
无论选择集合还是映射，这里都是在“以空间换时间”：最多额外保存线性数量的信息，换掉内层的重复扫描。
通用模板
下面的伪代码适合“用当前元素匹配历史信息”的单次扫描：
state = 空集合或空映射
for 当前元素 in 输入:
query_key = 从当前元素推导要找的键
if query_key 在 state 中:
用 state[query_key] 和当前元素构造答案
把当前元素对应的信息写入 state
循环中的核心不变量是：处理位置 i 之前，state 只描述位置 i 之前的元素。 因而一次命中天然对应“历史元素 + 当前元素”，不会误用未来信息。
为什么常常要先查后存
如果题目要求两个不同位置，必须先查询，再把当前元素存入哈希表。否则当前元素可能立刻匹配到自己。
以“两数之和”为例，当前值为 x 时要找 target - x。先查后存保证命中的下标严格早于当前位置；同时又不会漏掉 [3, 3] 这类需要两个相同数值的答案：第一个 3 先在查询失败后入表，第二个 3 再命中它。
复杂度应怎样表述
不同键可能得到相同的哈希位置，这叫哈希冲突。标准哈希容器会用链式结构或开放寻址等办法处理冲突，所以存在冲突不等于查询失效，也不改变通常所说的期望均摊 O(1) 结论。这一结论依赖合理的哈希函数和负载控制；极端构造下，单次操作仍可能退化到 O(n)。
因此，含 n 个元素的一次扫描通常写作期望时间 O(n)、额外空间 O(n)，而不是声称任何输入下都严格为线性时间。
模板变体
只记录存在性
用集合保存出现过的键。典型任务包括判重、寻找连续序列的起点，以及判断某个互补状态是否存在。
记录计数
用映射保存 键 → 次数。先统计再查询适合两个阶段的问题；边遍历边更新适合前缀状态、字符频次和在线计数。
记录位置或分组
用映射保存 键 → 下标 可以恢复答案位置；保存 特征 → 列表 可以把具有相同特征的元素分到同一组。此时真正需要设计的是“什么可以作为稳定且唯一代表一组信息的键”。
母题序列
建议按必学顺序练习。三题分别验证映射、规范化键和集合边界三个关键用法：
- 两数之和：把“寻找另一个数”改写为补数查询，掌握先查后存。
- 字母异位词分组：为每个字符串设计统一特征，把映射的值扩展为分组列表。
- 最长连续序列：用集合快速判断相邻值，只从序列起点向后扩展，避免重复工作。
常见误区
- 把所有输入预先入表，却没有处理“同一元素不能使用两次”的限制。
- 需要返回原下标时先排序，破坏了位置关系，又没有保留原始下标。
- 用映射下标访问来判断键是否存在，意外插入默认值；C++ 应优先使用
find，Python 应使用in。 - 只写“哈希操作是
O(1)”，忽略这是通常意义下的期望均摊复杂度。 - 问题依赖顺序、最值或排名时仍强行使用哈希表；这类需求往往更适合排序、二分或有序容器。
迁移方向
掌握哈希表后，可以沿三条路线继续迁移：
- “值 → 次数”迁移到前缀和计数：把前缀状态作为键，寻找可配对的历史前缀；
- “特征 → 分组”迁移到字符串规范化：排序后的字符串或字符频次数组可以成为分组键；
- “存在性集合”迁移到图搜索中的访问标记：集合用于阻止同一状态被重复扩展；
- 迁移到LRU 缓存：哈希表只负责按键定位节点，最近使用顺序由双向链表维护。
若题目还要求按大小关系查找、输出有序结果或维护区间边界，应转向排序与二分、双指针等框架，而不是继续增加哈希表中的状态。