数据结构与算法 / 系统课时
用哈希表把查找降到线性
用哈希表把查找降到线性
很多数组题慢在“为了确认另一个值是否出现过,又把数组扫一遍”。哈希表把这种重复查找改成一次线性扫描中的常数级查询,让配对、去重、计数和索引映射都能用同一套思路处理。
学习目标
- 识别“边扫描边查询已见元素”的哈希表信号
- 用哈希表把典型双重循环从 降到平均
- 区分集合、计数表和“值到索引”映射的用途
先找出嵌套扫描里的重复工作
以“两数之和”为例:给定数组 nums 和目标值 target,需要找到两个不同位置,使对应元素之和等于目标值。直接做法是枚举第一个位置,再向后寻找第二个位置;当数组长度为 时,最坏需要比较约 次。
真正需要回答的问题其实更简单:扫描到当前值 x 时,前面是否已经出现过 target - x?如果能快速回答这个问题,就不必再次扫描前缀。
哈希表适合的核心信号是:当前元素的决策依赖于“某个键以前是否出现、出现几次或对应哪个位置”。常见形式包括配对查找、去重、频次统计和索引映射。
边查边存完成两数之和
下面的实现使用字典保存“值到索引”的映射。顺序很重要:先查补数,再写入当前值,这样同一个位置不会被重复使用,同时也能正确处理 [3, 3] 这类重复值。
def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
# 当前元素处理完后再加入,保证两个索引不同
seen[x] = i
return []
print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 3], 6))预期输出:
[0, 1]
[0, 1]第一次扫描到 2 时,表里还没有 7,于是记录 {2: 0};扫描到 7 时,需要的补数是 2,可以立即命中并返回结果。每个元素只进入主循环一次。
根据题目问题选择哈希结构
哈希并不等于“统一使用字典”。如果只关心某个值是否出现过,用集合最直接;如果关心出现次数,用“值到次数”的映射;如果需要返回位置,则保存“值到索引”。
例如判断数组是否存在重复元素,只需维护集合:遇到已经存在的值即可结束。统计字符频次时,则需要把每个字符映射到累计次数。选择结构时应先问:后续查询需要的是存在性、次数,还是附加信息?
复杂度与边界
哈希方案通常使用 额外空间,换取平均 时间。相比不使用额外空间的双重循环,这是典型的“空间换时间”。
需要特别检查三类边界:重复值是否允许组成答案、同一元素能否使用两次、题目是否要求保留原始顺序或索引。如果题目要求返回索引,就不能只保存集合;如果需要统计所有配对,也不能找到第一个答案后立即返回。
当输入已经排序,且问题只要求寻找一对值时,双指针可能用 额外空间完成;但对未排序数组中的快速存在性查询,哈希表通常是更直接的线性扫描套路。