数据结构与算法 / 系统课时

用哈希表把查找降到线性

用哈希表把查找降到线性

很多数组题慢在“为了确认另一个值是否出现过,又把数组扫一遍”。哈希表把这种重复查找改成一次线性扫描中的常数级查询,让配对、去重、计数和索引映射都能用同一套思路处理。

学习目标

  • 识别“边扫描边查询已见元素”的哈希表信号
  • 用哈希表把典型双重循环从 O(n2)O(n^2) 降到平均 O(n)O(n)
  • 区分集合、计数表和“值到索引”映射的用途

先找出嵌套扫描里的重复工作

以“两数之和”为例:给定数组 nums 和目标值 target,需要找到两个不同位置,使对应元素之和等于目标值。直接做法是枚举第一个位置,再向后寻找第二个位置;当数组长度为 nn 时,最坏需要比较约 n2n^2 次。

真正需要回答的问题其实更简单:扫描到当前值 x 时,前面是否已经出现过 target - x?如果能快速回答这个问题,就不必再次扫描前缀。

哈希表适合的核心信号是:当前元素的决策依赖于“某个键以前是否出现、出现几次或对应哪个位置”。常见形式包括配对查找、去重、频次统计和索引映射。

边查边存完成两数之和

下面的实现使用字典保存“值到索引”的映射。顺序很重要:先查补数,再写入当前值,这样同一个位置不会被重复使用,同时也能正确处理 [3, 3] 这类重复值。

python
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))

预期输出:

text
[0, 1]
[0, 1]

第一次扫描到 2 时,表里还没有 7,于是记录 {2: 0};扫描到 7 时,需要的补数是 2,可以立即命中并返回结果。每个元素只进入主循环一次。

根据题目问题选择哈希结构

哈希并不等于“统一使用字典”。如果只关心某个值是否出现过,用集合最直接;如果关心出现次数,用“值到次数”的映射;如果需要返回位置,则保存“值到索引”。

例如判断数组是否存在重复元素,只需维护集合:遇到已经存在的值即可结束。统计字符频次时,则需要把每个字符映射到累计次数。选择结构时应先问:后续查询需要的是存在性、次数,还是附加信息?

复杂度与边界

哈希方案通常使用 O(n)O(n) 额外空间,换取平均 O(n)O(n) 时间。相比不使用额外空间的双重循环,这是典型的“空间换时间”。

需要特别检查三类边界:重复值是否允许组成答案、同一元素能否使用两次、题目是否要求保留原始顺序或索引。如果题目要求返回索引,就不能只保存集合;如果需要统计所有配对,也不能找到第一个答案后立即返回。

当输入已经排序,且问题只要求寻找一对值时,双指针可能用 O(1)O(1) 额外空间完成;但对未排序数组中的快速存在性查询,哈希表通常是更直接的线性扫描套路。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用哈希表把查找降到线性

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通