力扣百题通

01-哈希表

6分钟阅读

01 · 哈希表

来源： 编译自 labuladong 框架 + 代码随想录体系 + 灵茶山艾府题单
核心价值： 将查找时间从 O(n) 降低到 O(1)

一、本质理解

哈希表（Hash Table）的本质是 数组 + 哈希函数。
labuladong 将其归类为”数组”的延伸——用哈希函数将 key 映射到数组索引，实现 O(1) 的查找、插入、删除。

核心思想：空间换时间。 用额外的内存空间换取更快的查找速度。

二、四大应用场景

场景说明典型题目
查找快速判断元素是否存在1. 两数之和
去重判断元素是否重复出现128. 最长连续序列
计数统计元素出现次数49. 字母异位词分组
分组按规则将元素归类49. 字母异位词分组、560. 和为 K 的子数组

本质套路： 什么时候用哈希表？
→ 当你需要快速查找某个元素是否出现过，或者需要统计某个值的出现次数时，考虑用哈希表。

三、Python 哈希表工具对比

工具适用场景示例
dict通用键值映射seen[num] = i
defaultdict自动初始化默认值graph defaultdict(list)
Counter统计频次Counter(nums).most_common(k)
set只关心存在性seen = set()

四、核心模板

模板 1：两数之和（查找互补元素）

def two_sum(nums, target):
    seen = {}  # 值 -> 索引
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

变形： 如果只需要判断是否存在，用 set 即可。

模板 2：字母异位词分组（排序分组）

from collections import defaultdict
 
def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # 排序后的元组作为 key
        groups[key].append(s)
    return list(groups.values())

优化： 用字符计数元组代替排序（当字符串很长时更快）：

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        groups[tuple(count)].append(s)
    return list(groups.values())

模板 3：最长连续序列（用集合去重 + 找起点）

def longest_consecutive(nums):
    nums_set = set(nums)
    longest = 0
    
    for num in nums_set:
        # 关键优化：只从序列起点开始查找
        if num - 1 not in nums_set:
            current = num
            length = 1
            while current + 1 in nums_set:
                current += 1
                length += 1
            longest = max(longest, length)
    
    return longest

核心优化： 只从 num-1 不在集合中 的元素开始查找，确保每个元素只被遍历一次，O(n) 时间。

模板 4：前缀和 + 哈希表（子数组和问题）

from collections import defaultdict
 
def subarray_sum(nums, k):
    prefix_sum = 0
    count = 0
    sum_count = defaultdict(int)
    sum_count[0] = 1  # 前缀和为 0 出现 1 次（空数组）
    
    for num in nums:
        prefix_sum += num
        # 如果存在 prefix_sum - k，说明有子数组和为 k
        count += sum_count[prefix_sum - k]
        sum_count[prefix_sum] += 1
    
    return count

五、Hot 100 哈希表题目清单

题号题目难度核心思路建议用时
1两数之和Easy哈希表存遍历过的值，查找互补25 min
49字母异位词分组Medium排序/计数作 key，分组收集30 min
128最长连续序列Medium集合去重，只从序列起点开始查35 min

其他用到哈希表的题目

题号题目哈希用途
560和为 K 的子数组前缀和 + 哈希计数
76最小覆盖子串哈希表统计字符需求
3无重复最长子串哈希集合记录窗口内字符
146LRU 缓存哈希表存 key->node 映射
347前 K 个高频元素Counter 统计频次

六、易错点与技巧

  1. Key 的选择：必须是可哈希的（immutable），list 不能做 key，tuple 可以
  2. defaultdict vs dict：计数或分组时用 defaultdict 省去判空步骤
  3. Counter 的 most_common(k) 直接返回 Top K，底层用堆实现
  4. 集合去重：set(nums) 比用 dict 去重更简洁高效
  5. 边遍历边查：两数之和类问题中，“边遍历边查”比”先全存再查”更高效

七、复杂度总结

操作平均时间复杂度最坏时间复杂度空间复杂度
查找O(1)O(n)O(n)
插入O(1)O(n)O(n)
删除O(1)O(n)O(n)

注意： Python 3 的 dict 实现经过高度优化，实际性能非常好。最坏情况 O(n) 只在哈希冲突严重时发生。

八、参考与延伸

关系图谱

反向链接