30 秒速览

  • 什么时候用：需要快速查找、去重、计数、分组
  • 核心思想：用空间换时间，通过 key 直接计算存储位置
  • 时间复杂度：平均 O(1) 查找/插入/删除
  • 空间复杂度：O(n)

一、直觉建立

图书馆找书

想象你在一个拥有 100 万本书的图书馆找一本书：

方法一：线性查找

问：《算法导论》在哪？
答：从第 1 排开始一本本找吧...
时间：平均 50 万次 → O(n)

方法二：哈希表

1. 听到书名：《算法导论》
2. 脑海中计算：hash("算法导论") = 42
3. 直接去第 42 号书架取书
时间：O(1)

关键洞察：哈希表把"任意类型的 key"转换成"数组下标"，实现 O(1) 访问。

生活中的哈希表

字典查词：按首字母 A-Z 分章节，直接翻到对应章节 学生档案：学号 % 100 = 柜子编号 身份证查信息：用身份证号作为 key，直接定位

Python 中的哈希表家族

# 基础款
dict    # 通用键值对映射
set     # 只存 key，用于判断存在性和去重

# 增强款（collections 模块）
Counter     # 专门用于计数统计
defaultdict # 带默认值，避免 KeyError

# 选择指南
存储键值对 → dict
只判断存在性 → set
需要计数 → Counter
需要默认值 → defaultdict

二、核心原理

哈希函数

哈希表 = 哈希函数 + 数组

位置 index = hash(key) % 数组大小

哈希冲突

不同 key 可能计算出相同 index。

解决方案：

  1. 链地址法：同一位置的元素用链表串起来
  2. 开放地址法：占用了就找下一个空位

Python 的 dict 使用开放地址法的变体。

三、三大场景

场景 1：快速查找

触发信号：需要判断某元素是否存在

# 用 set 实现快速查找
visited = set()
if target in visited:  # O(1)
    ...

# 用 dict 实现 key-value 查找
cache = {}
if key in cache:  # O(1)
    return cache[key]

场景 2：计数统计

触发信号：需要统计每个元素出现的次数

from collections import Counter

# 方法一：Counter
count = Counter(nums)

# 方法二：手动用 dict
count = {}
for num in nums:
    count[num] = count.get(num, 0) + 1

# 方法三：defaultdict
from collections import defaultdict
count = defaultdict(int)
for num in nums:
    count[num] += 1

场景 3：分组

触发信号：需要按某个特征把元素分组

from collections import defaultdict

# 按字符串的字母组成分组（异位词）
groups = defaultdict(list)
for word in words:
    key = ''.join(sorted(word))  # 排序后作为 key
    groups[key].append(word)

# 按数字的某特征分组
groups = defaultdict(list)
for num in nums:
    key = num % k
    groups[key].append(num)

四、典型例题

例题 1：LC 1. 两数之和

题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的两个整数，并返回它们的数组下标。

示例：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]

思路

用哈希表记录已经遍历过的数字及其索引，查找 target - nums[i] 是否存在。

代码

def twoSum(nums: list[int], target: int) -> list[int]:
    seen = {}  # 值 → 索引

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

    return []

复杂度：时间 O(n)，空间 O(n)

例题 2：LC 49. 字母异位词分组

题目：给你一个字符串数组，请你将字母异位词组合在一起。字母异位词是由相同字母重新排列形成的字符串。

示例：

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

思路

字母异位词排序后相同，用排序后的字符串作为 key 分组。

代码

from collections import defaultdict

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)

    for s in strs:
        key = ''.join(sorted(s))  # 排序后作为 key
        groups[key].append(s)

    return list(groups.values())

复杂度：时间 O(n * k log k)，k 是字符串最大长度

例题 3：LC 128. 最长连续序列

题目：给定一个未排序的整数数组 nums，找出数字连续的最长序列的长度。要求算法的时间复杂度为 O(n)。

示例：

输入：nums = [100,4,200,1,3,2]
输出：4  （最长连续序列是 [1, 2, 3, 4]）

思路

关键观察：对于每个数，只有当它是一个序列的起点（num-1 不存在）时才开始计算长度。

代码

def longestConsecutive(nums: list[int]) -> int:
    num_set = set(nums)
    max_len = 0

    for num in num_set:
        # 只有当 num 是序列起点时才计算
        if num - 1 not in num_set:
            curr_num = num
            curr_len = 1

            while curr_num + 1 in num_set:
                curr_num += 1
                curr_len += 1

            max_len = max(max_len, curr_len)

    return max_len

复杂度：时间 O(n)，每个数最多被访问两次

例题 4：LC 349. 两个数组的交集

题目：给定两个数组，计算它们的交集。

代码

def intersection(nums1: list[int], nums2: list[int]) -> list[int]:
    set1 = set(nums1)
    set2 = set(nums2)
    return list(set1 & set2)  # 交集

复杂度：时间 O(m + n)

例题 5：LC 454. 四数相加 II

题目：给定四个整数数组 nums1, nums2, nums3, nums4，计算有多少个元组 (i, j, k, l) 使得 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0。

思路

把四数之和分成两组：先计算 nums1 + nums2 的所有可能和，再查找 -(nums3 + nums4)。

代码

from collections import Counter

def fourSumCount(nums1: list[int], nums2: list[int],
                 nums3: list[int], nums4: list[int]) -> int:
    # 统计 nums1 + nums2 的所有可能和
    sum12 = Counter()
    for a in nums1:
        for b in nums2:
            sum12[a + b] += 1

    # 查找 -(nums3 + nums4) 在 sum12 中出现的次数
    result = 0
    for c in nums3:
        for d in nums4:
            result += sum12[-(c + d)]

    return result

复杂度：时间 O(n²)，空间 O(n²)

例题 6：LC 383. 赎金信

题目：给你两个字符串 ransomNote 和 magazine，判断 ransomNote 能不能由 magazine 里面的字符构成。

代码

from collections import Counter

def canConstruct(ransomNote: str, magazine: str) -> bool:
    count = Counter(magazine)

    for c in ransomNote:
        if count[c] == 0:
            return False
        count[c] -= 1

    return True

复杂度：时间 O(m + n)

例题 7：LC 560. 和为 K 的子数组（前缀和 + 哈希表）

详见前缀和专题。核心是用哈希表记录前缀和出现的次数，快速找到满足条件的前缀和。

五、哈希表 vs 其他数据结构

操作数组哈希表有序结构（Tree）
查找O(n)O(1)O(log n)
插入O(n)O(1)O(log n)
删除O(n)O(1)O(log n)
有序遍历O(n log n)O(n log n)O(n)
范围查询O(n)O(n)O(log n + k)

选择：

  • 只需要快速查找 → 哈希表
  • 需要有序遍历/范围查询 → 平衡树（如 SortedDict）
  • 数据量小 → 数组够用

六、常见错误与陷阱

错误 1：使用可变对象作为 key

# 错误：list 不能作为 dict 的 key
d = {}
d[[1, 2]] = 3  # TypeError: unhashable type: 'list'

# 正确：用 tuple
d = {}
d[(1, 2)] = 3  # OK

错误 2：修改正在遍历的 dict/set

# 错误：遍历时修改
d = {1: 'a', 2: 'b', 3: 'c'}
for k in d:
    if k == 2:
        del d[k]  # RuntimeError

# 正确：先收集要删除的 key
to_delete = [k for k in d if k == 2]
for k in to_delete:
    del d[k]

错误 3：Counter 的陷阱

c = Counter(['a', 'b'])
print(c['c'])  # 输出 0，而不是 KeyError！

# 如果需要判断是否存在，用 in
if 'c' in c:  # False
    ...

七、复盘清单

触发信号

  • 需要快速判断元素是否存在
  • 需要去重
  • 需要统计频率
  • 需要按特征分组
  • 需要记录已访问的元素

边界条件

  • 空输入
  • 重复元素
  • 负数作为 key
  • 字符串作为 key

常见错误

  • 使用不可哈希的对象作为 key
  • 遍历时修改 dict/set
  • Counter 访问不存在的 key 返回 0
  • defaultdict 忘记指定默认工厂函数

八、题目清单

基础题

题号题目难度考点
1两数之和Easy快速查找
217存在重复元素Easyset 去重
349两个数组的交集Easyset 交集
383赎金信EasyCounter
242有效的字母异位词EasyCounter 比较

进阶题

题号题目难度考点
49字母异位词分组Medium分组
128最长连续序列Mediumset + 起点
454四数相加 IIMedium分组统计
560和为 K 的子数组Medium前缀和+哈希
3无重复字符的最长子串Medium滑动窗口+set