引言

本文是一篇面向 LeetCode 哈希表专题的速成笔记，适合需要在短时间内建立题感、掌握模板、快速覆盖 Hot100 高频题型的读者。

哈希表题的核心不在于 API，而在于一句话:

把“需要反复查询的信息”提前存起来，把原本重复的查找变成 O(1) 级别的访问。

学习这类题时，最重要的不是记住某一道题的答案，而是记住几个固定问题:

  • 这题要查什么？
  • 哈希表的 key 存什么？
  • 哈希表的 value 存什么？
  • 什么时候更新答案？
  • 是否需要和滑动窗口、链表等结构配合？

文章会围绕 LeetCode Hot100 中几道典型题展开:

题号 题目 核心套路
1 两数之和 补数查找
49 字母异位词分组 分组 key
128 最长连续序列 set 判存在
3 无重复字符的最长子串 滑动窗口
76 最小覆盖子串 滑动窗口 + 计数
146 LRU 缓存 哈希表 + 双向链表

本文使用 Python 作为示例语言。

一、哈希表的理论基础

1.1 什么是哈希表

在 Python 里，最常见的哈希表就是：

  • dict
  • set

它们的共同特点是：

  • 平均时间复杂度下，插入、删除、查询都接近 O(1)
  • 特别适合做“查重”“计数”“映射”“快速判断是否存在”

例如：

seen = set()
count = {}

seen.add(3)
3 in seen           # True

count["a"] = count.get("a", 0) + 1

1.2 哈希表解决的本质问题

很多题如果暴力做，都会出现这样的问题：

  • 反复查某个元素是否出现过
  • 反复统计某个元素出现次数
  • 反复找“某个条件对应的另一个值”

这类“反复查询”的动作，本来可能是 O(n)，一旦放进哈希表，就能降到接近 O(1)。

所以你可以把哈希表理解成一句话：

用空间换时间。

1.3 先记住这几个代码模板

哈希表题速成时，不建议一开始就追求变化很多的写法。先把下面几个模板记熟，遇到题再判断应该套哪一种。

模板一：计数

count = {}
for x in nums:
    count[x] = count.get(x, 0) + 1

关键词：

  • 出现次数
  • 字符频率
  • 数量是否足够
  • 两个对象是否由相同元素组成

模板二：判断是否存在

seen = set()
for x in nums:
    if x in seen:
        ...
    seen.add(x)

关键词：

  • 是否出现过
  • 去重
  • 快速判断在不在

模板三：记录“值 -> 下标”

index_map = {}
for i, x in enumerate(nums):
    index_map[x] = i

关键词：

  • 找下标
  • 找配对
  • 找之前出现过的位置

模板四：记录“状态 -> 位置”

first_pos = {0: -1}

关键词：

  • 前缀和
  • 子数组
  • 某种状态第一次出现的位置

模板五：窗口内计数

left = 0
window = {}

for right, ch in enumerate(s):
    window[ch] = window.get(ch, 0) + 1

    while 窗口不合法:
        window[s[left]] -= 1
        left += 1

关键词：

  • 子串
  • 最长
  • 最短
  • 覆盖
  • 无重复

速成时可以先记一句话:

题目关键词 优先想到
找另一个数 补数查找
出现次数 计数表
分成几组 设计分组 key
是否存在 set
子串 / 窗口 滑动窗口 + 哈希表
O(1) 设计 哈希表 + 其他结构

Python 里做 key 的两个注意点

哈希表的 key 必须是可哈希对象。

list 是可变对象，不能直接作为 dict 的 key：

count = [1, 0, 2]
groups[count] = ["eat"]  # TypeError: unhashable type: 'list'

如果需要把一个列表状态作为 key，要先转成 tuple：

count = [1, 0, 2]
key = tuple(count)
groups[key] = ["eat"]

字符串排序时也要注意：

key = "".join(sorted(word))

这里用的是 sorted(word)，它会返回一个新的列表。

不要写成：

key = word.sort()

原因有两个：

  • str 没有 .sort() 方法
  • .sort() 是列表的原地排序方法，返回值是 None

二、一眼识别哈希表的信号

很多人不会哈希表题，不是不会写 dict，而是不会判断什么时候该用它。

下面这些信号一出现，你就应该优先考虑哈希表：

2.1 题目在问“是否存在某个配对 / 某个补数”

典型题：

  • 两数之和

关键词：

  • 是否存在
  • 找另一个数
  • 满足和 / 差 / 条件

这类题通常是“边遍历边查表”。

2.2 题目在问“频次”

典型题：

  • 字母异位词分组
  • 有效的字母异位词

关键词：

  • 出现次数
  • 统计字符
  • 统计元素

这类题的核心是“计数”。

2.3 题目在问“去重 / 是否出现过”

典型题：

  • 最长连续序列

关键词：

  • 是否存在
  • 连续
  • 去重

这类题通常用 set。

2.4 题目在问“子串 / 窗口内状态”

典型题：

  • 无重复字符的最长子串
  • 最小覆盖子串

关键词：

  • 子串
  • 窗口
  • 覆盖
  • 无重复
  • 最长 / 最短

这类题经常是“滑动窗口 + 哈希表”。

2.5 题目要求你设计数据结构

典型题：

  • LRU 缓存

关键词：

  • 设计
  • get / put
  • 最近最少使用
  • 要求 O(1)

这类题通常不是单纯哈希表，而是“哈希表 + 其他结构”组合。

三、六类高频套路与模板

3.1 套路一：补数查找

适用场景：

  • 找两数和
  • 找满足某种关系的配对

模板：

def template(nums, target):
    pos = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in pos:
            return [pos[need], i]
        pos[x] = i

思路：

  • 一边遍历当前值 x
  • 一边查“我需要的那个值 need 在不在表里”

3.2 套路二：频次统计

适用场景：

  • 统计字符出现次数
  • 判断两个对象是否由相同元素构成

模板：

def build_count(items):
    count = {}
    for x in items:
        count[x] = count.get(x, 0) + 1
    return count

思路：

  • 哈希表的键是元素
  • 哈希表的值是频次

3.3 套路三：分组

适用场景：

  • 按某种“标准化结果”分组

模板：

def group_by_key(items):
    groups = {}
    for item in items:
        key = normalize(item)
        groups.setdefault(key, []).append(item)
    return list(groups.values())

关键点不在分组，而在于：

如何构造一个能代表这一组特征的 key。

3.4 套路四：集合判重 + 连续性判断

适用场景：

  • 连续序列
  • 去重后快速判断某个数是否存在

模板：

def longest_consecutive(nums):
    s = set(nums)
    ans = 0

    for x in s:
        if x - 1 not in s:
            cur = x
            length = 1
            while cur + 1 in s:
                cur += 1
                length += 1
            ans = max(ans, length)

    return ans

关键技巧：

  • 只从“连续段起点”开始扩展
  • 否则会重复计算

3.5 套路五：滑动窗口 + 哈希表

适用场景：

  • 最长无重复子串
  • 最小覆盖子串
  • 固定 / 可变窗口题

模板：

def sliding_window(s):
    left = 0
    count = {}

    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1

        while window_invalid(count):
            count[s[left]] -= 1
            left += 1

        update_answer(left, right)

核心思维：

  • right 负责扩张窗口
  • left 负责收缩窗口
  • 哈希表负责维护“窗口当前状态”

3.6 套路六：哈希表 + 双向链表

适用场景：

  • LRU 缓存
  • LFU 之类设计题

模板思路：

  • 哈希表：key -> 节点
  • 双向链表：维护使用顺序

为什么要组合？

  • 只用哈希表能做到快速查找
  • 但做不到快速调整“最近使用顺序”
  • 双向链表刚好补这个缺口

四、Hot100 经典例题拆解

4.1 1. 两数之和

题目本质

对于每个数 x，我们都在问：

target - x 出现过吗？

这就是最典型的“补数查找”。

为什么用哈希表

如果每次都去后面找补数，时间复杂度是 O(n^2)。

如果把已经遍历过的数存进哈希表，就能在 O(1) 时间检查补数是否存在。

代码

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        pos = {}

        for i, x in enumerate(nums):
            need = target - x
            if need in pos:
                return [pos[need], i]
            pos[x] = i

复杂度

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

这题记住什么

遇到“找另一个数”，优先想“补数能不能放进哈希表里查”。

4.2 49. 字母异位词分组

题目本质

如果两个字符串互为字母异位词，它们排序后一定相同。

例如：

"eat" -> "aet"
"tea" -> "aet"

所以这题的关键是：

为每个字符串构造一个统一的分组 key。

两种常见 key

写法一：排序后的字符串
key = "".join(sorted(s))

这里有一个 Python 小坑：

  • sorted(s) 会把字符串拆成字符列表并返回排序结果
  • "".join(...) 再把字符列表拼回字符串
  • 字符串本身不能调用 .sort()

所以应该写：

key = "".join(sorted(s))

不要写：

key = s.sort()
写法二：26 个字母频次数组

适合你想更深入理解“计数型 key”的时候。

如果使用 26 个字母频次数组做 key，要记得把 list 转成 tuple：

count = [0] * 26
for ch in s:
    count[ord(ch) - ord("a")] += 1

key = tuple(count)

因为 list 不能作为 dict 的 key，tuple 才可以。

代码

from typing import List


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}

        for s in strs:
            key = "".join(sorted(s))
            groups.setdefault(key, []).append(s)

        return list(groups.values())

复杂度

设单个字符串平均长度为 k：

  • 时间复杂度：O(n * k log k)
  • 空间复杂度：O(n * k)

这题记住什么

分组题的核心不是“怎么存”，而是“怎么设计分组 key”。

4.3 128. 最长连续序列

题目本质

这题不是排序题，而是“快速判断某个数在不在”的题。

只要能快速判断：

  • x - 1 在不在
  • x + 1 在不在

这题就能做出来。

为什么用 set

用 set(nums) 之后，判断一个数是否存在就是 O(1)。

真正的关键技巧是：

只从连续段的起点开始枚举。

如果 x - 1 存在，那说明 x 不是起点，就跳过。

代码

from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        ans = 0

        for x in s:
            if x - 1 in s:
                continue

            cur = x
            length = 1

            while cur + 1 in s:
                cur += 1
                length += 1

            ans = max(ans, length)

        return ans

复杂度

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

这题记住什么

集合题常见关键不是“存所有元素”，而是“找到避免重复遍历的条件”。

4.4 3. 无重复字符的最长子串

题目本质

题目在求：

一个窗口里，所有字符都不能重复。

这类题最经典的做法就是“滑动窗口 + 哈希表计数”。

核心思路

  • right 向右扩张，把字符加入窗口
  • 如果窗口里出现重复字符，就移动 left 缩小窗口
  • 在整个过程中维护最大长度

代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        count = {}
        ans = 0

        for right, ch in enumerate(s):
            count[ch] = count.get(ch, 0) + 1

            while count[ch] > 1:
                count[s[left]] -= 1
                left += 1

            ans = max(ans, right - left + 1)

        return ans

复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(|字符集|)

这题记住什么

窗口题里，哈希表维护的是“窗口状态”，不是全局状态。

4.5 76. 最小覆盖子串

题目本质

这题和上一题一样，也是滑动窗口。

但难点在于：

  • 不是“不能重复”
  • 而是“窗口必须覆盖目标串的所有字符，并且数量也要够”

核心思路

先统计目标串 t 里每个字符需要多少个，再在窗口中动态统计当前已有多少个。

当窗口已经满足条件时，就尽量收缩左边界，寻找更短答案。

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = {}
        for ch in t:
            need[ch] = need.get(ch, 0) + 1

        window = {}
        need_kinds = len(need)
        valid = 0
        left = 0
        start = 0
        min_len = float("inf")

        for right, ch in enumerate(s):
            if ch in need:
                window[ch] = window.get(ch, 0) + 1
                if window[ch] == need[ch]:
                    valid += 1

            while valid == need_kinds:
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    start = left

                left_ch = s[left]
                if left_ch in need:
                    if window[left_ch] == need[left_ch]:
                        valid -= 1
                    window[left_ch] -= 1
                left += 1

        return "" if min_len == float("inf") else s[start:start + min_len]

复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(|字符集|)

这题记住什么

滑动窗口难题的关键不是代码长，而是先想清楚“窗口什么时候算合法，什么时候该收缩”。

4.6 146. LRU 缓存

题目本质

题目要求：

  • get 是 O(1)
  • put 是 O(1)
  • 最近访问过的元素要更靠前
  • 容量满了时，淘汰最久没使用的元素

这说明：

  • 你需要快速按 key 找到节点
  • 你还需要快速调整节点在“使用顺序”中的位置

所以只用哈希表不够，必须配合双向链表。

结构设计

  • 哈希表：key -> node
  • 双向链表：
    • 头部附近表示最近使用
    • 尾部附近表示最久未使用

代码

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}

        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_to_front(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node: Node) -> None:
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _move_to_front(self, node: Node) -> None:
        self._remove_node(node)
        self._add_to_front(node)

    def _remove_lru(self) -> Node:
        lru = self.tail.prev
        self._remove_node(lru)
        return lru

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1

        node = self.cache[key]
        self._move_to_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._move_to_front(node)
            return

        node = Node(key, value)
        self.cache[key] = node
        self._add_to_front(node)

        if len(self.cache) > self.capacity:
            lru = self._remove_lru()
            del self.cache[lru.key]

复杂度

  • 时间复杂度：get 和 put 都是 O(1)
  • 空间复杂度：O(capacity)

这题记住什么

设计题里，哈希表常常负责“定位”，其他结构负责“维护顺序 / 关系”。

五、刷题时的复盘清单

每做完一道哈希表题，建议你问自己五个问题：

5.1 我到底在查什么

是查：

  • 某个值是否存在
  • 某个值出现了几次
  • 某个状态第一次出现在哪
  • 某个 key 对应哪个对象

先把“查什么”说清楚，哈希表的键值设计才会自然。

5.2 哈希表的 key 应该是什么

常见 key：

  • 单个数字
  • 单个字符
  • 排序后的字符串
  • 频次数组转成元组
  • key

很多题的难点，不是哈希表本身，而是 key 设计。

5.3 哈希表的 value 应该是什么

常见 value：

  • 下标
  • 次数
  • 列表
  • 节点
  • 最早位置

5.4 我是不是重复计算了

比如最长连续序列里，如果不是只从起点开始扩展，就会重复算很多次。

很多 O(n) 题和 O(n^2) 题的区别，往往就在这一点。

5.5 这题是不是哈希表和别的套路结合

哈希表很少单独考，它经常和这些思路组合出现：

  • 哈希表 + 滑动窗口
  • 哈希表 + 双指针
  • 哈希表 + 链表
  • 哈希表 + 前缀和

如果你已经想到“要查表”，下一步就要想“还需要哪个结构一起配合”。

六、文章总结

6.1 哈希表专题速查表

题型 判断关键词 哈希表里存什么 典型题
补数查找 两数之和、找另一个数、满足 target 值 -> 下标 1. 两数之和
频次统计 出现次数、字符数量、是否足够 元素 -> 次数 49. 字母异位词分组
分组归类 分组、同一类、异位词 标准化 key -> 列表 49. 字母异位词分组
集合判存在 是否存在、连续、去重 set(nums) 128. 最长连续序列
滑动窗口 子串、最长、最短、覆盖、无重复 窗口内元素 -> 次数 3. 无重复字符的最长子串、76. 最小覆盖子串
结构设计 get、put、O(1)、最近使用 key -> node 146. LRU 缓存

6.2 Hot100 练习顺序

顺序 题目 建议掌握点
1 1. 两数之和 边遍历边查补数
2 49. 字母异位词分组 用排序字符串或频次数组做 key
3 128. 最长连续序列 只从连续段起点开始扩展
4 3. 无重复字符的最长子串 用窗口计数维护无重复状态
5 76. 最小覆盖子串 用 need、window、valid 判断窗口是否合法
6 146. LRU 缓存 哈希表负责定位，双向链表负责顺序

6.3 考前记忆版

看到题目在问 先想什么
找两个数是否满足条件 need = target - x
判断是否出现过 set
统计字符或数字次数 dict.get(x, 0) + 1
把字符串分成几组 设计一个统一的 key
子串最长 / 最短 滑动窗口
要求 O(1) 查询和更新 哈希表配合链表或其他结构

最后按这三步检查一道哈希表题：

  1. 先判断题目是在查存在、查次数、查位置，还是查窗口状态。
  2. 再确定哈希表的 key 和 value。
  3. 最后看是否需要搭配滑动窗口、链表、前缀和等其他结构。
# leetcode # 散列表
Logo
亚马逊云科技技术品牌专区

更多推荐

Java分布式架构设计方法

服务拆分后，服务间的通信成为关键。事件驱动架构是另一种有效解耦和数据同步的方式，服务通过发布/订阅领域事件进行通信，借助Apache Kafka或RabbitMQ等消息中间件，可以实现事件的可靠传递与异步处理，提升系统整体响应能力。从业务拆分出发，选择恰当的通信与治理模式，妥善处理数据一致性，并构建完善的运维支撑体系。随着云原生理念的深入，Serverless、Service Mesh等新技术也在

avatar 亚马逊云科技技术品牌专区
cover

人工智能赋能新型工业化实施路径方法论

avatar 亚马逊云科技技术品牌专区

主动推理-人工海马

2026年07月04日 00:21发言人00:00制造能够思考的机器是人类长久以来的梦想，但这到底意味着什么呢？智能的一个显著特性是能够泛化知识，并灵活地将其应用于新情况。这种泛化确实是现代机器学习的核心问题之一。在这段视频中，我们将探讨如何汲取海马体负责记忆和导航的大脑结构的生物学组织，来构建一个能够学习构建抽象和泛化的计算模型。我们将探索这个模型带给我们关于大脑自身及人工智能领域的启示。发言人

avatar 亚马逊云科技技术品牌专区