LeetCode（一）：哈希表

哈希表是工具箱里的性价比之王：每个元素只占用常数级别的内存，却能把“这个值存在吗？”的查询开销降到接近一条 CPU 指令。很多暴力解法复杂度高达 $O(n^2)$ ，但只要用上哈希表，往往就能直接优化到 $O(n)$ 的一次遍历。

这是 LeetCode 算法精讲系列 的开篇，从零开始帮你建立对哈希表的直观理解，并通过四道经典题——两数之和、字母异位词分组、无重复字符的最长子串、前 K 个高频元素——提炼出可以反复使用的通用解题套路。

一、哈希表究竟是什么#

哈希表的核心是一个底层数组，用来存储 (key, value) 键值对。它的关键机制在于 哈希函数：无论 key 是什么类型，哈希函数都能把它转换成一个整数下标，告诉你这个键值对应该放在数组的哪个位置。

这种设计带来了三个重要特性：

• 确定性：同一个 key 永远会映射到同一个槽位，这是查找操作能正常工作的基础。
• 平均 $O(1)$ ：只要哈希函数设计合理，插入、查找和删除操作的时间复杂度不会随着数据量 $n$ 增加而变大。
• 最坏 $O(n)$ ：如果大量 key 都挤到同一个槽位，性能会退化成线性扫描。不过这种情况一般只会在输入恶意构造或者哈希函数设计糟糕时发生，实际工程中很少见。

冲突无法避免#

两个不同的 key 有可能映射到同一个槽位，这就是所谓的 冲突（collision）。解决冲突的方法主要有两种：

• 链式法（Separate Chaining）：每个槽位挂一个链表（或者平衡树），冲突的元素直接加到链表里。 Java 的 HashMap 和 C++ 的 std::unordered_map 都是这么干的。
• 开放寻址（Open Addressing）：每个槽位只存一个元素，发生冲突时按顺序探测下一个槽位（比如 slot+1、slot+2……），直到找到空位为止。 Python 的 dict 和 Go 的 map 就用这种策略。

虽然我们很少需要自己实现冲突处理逻辑，但理解这些机制很重要。它能帮你搞清楚两件事：为什么哈希表有时候会慢于 $O(1)$ ，以及为什么设计一个靠谱的哈希函数如此关键。

哈希表 vs 其他选择#

为什么选哈希表，而不是排序数组或者普通数组？

随着 $n$ 增大，差距非常明显。比如 $n = 1000$ 时，线性扫描每次查找要比较约 1000 次，二分查找约 10 次，而哈希查找只需约 1 次。不过天下没有免费的午餐，哈希表的代价是内存占用。 Python 的 dict 比裸数组多花大约 8–16 倍的字节，因为它需要存储哈希值、键、值，还得保持稀疏以减少冲突。

选哪种结构#

动手写代码前，先搞清楚实际需求：

简单说就是数组 > set > map，内存占用从低到高。能用轻量级结构就别选复杂的，具体看下面的对应关系：

Python 的 set 和 dict 底层实现是一样的，选哪个主要看语义——代码越贴近意图，读起来越顺，调试也越省心。

二、两数之和：互补搜索模式#

LeetCode 1. 给定一个数组 nums 和一个目标值 target，找出数组中两个数的下标，使它们的和等于 target。保证有且仅有一个解，同一个元素不能重复使用。

1
2

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

先写暴力解#

最朴素的做法是双重循环——$O(n^2)$ 时间，$O(1)$ 空间：

1
2
3
4
5
6
7

def two_sum_brute(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

当 $n = 10^4$ 时大约要做 5000 万次比较。可以做得更好。

哈希表的思维转换#

从左到右扫描数组时，每遇到一个 num，问题不再是“num 是否在数组里”，而是 “我之前是否已经见过 target - num？” 如果见过，就找到了答案。我们用一个 value → index 的映射表来记录所有已经遍历过的数字。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from typing import List

def two_sum(nums: List[int], target: int) -> List[int]:
    """单次遍历的哈希表解法。时间 O(n)，空间 O(n)。"""
    seen: dict[int, int] = {}          # value -> 最早出现的下标

    for i, num in enumerate(nums):
        complement = target - num
        # 先查再插：避免把 num 和它自己配成一对。
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

    return []   # 题目保证有解，理论上走不到这里

需要留意两个细节：

• 先查后插。如果先插入 seen[num] = i 再检查，像 nums = [3, 0, 0]、target = 6 这样的输入可能会让某个元素和自己配对。
• 返回顺序。seen[complement] 是更早的索引，必须放在前面，即 [seen[complement], i]。

这种思路的核心是将问题从“查找是否存在”转化为“查找是否曾经见过”。

为什么复杂度是 $O(n)$ #

外层循环总共跑 $n$ 次，每次迭代只涉及一次字典查找和可能的一次插入操作。这两者的平均时间复杂度都是 $O(1)$ 。因此，总时间复杂度为 $O(n)$ ，而空间复杂度也是 $O(n)$ ，因为字典最多存储 $n$ 个键值对。

对于未排序的数组来说，时间和空间复杂度已经无法同时再优化了。如果数组事先排好序，可以用双指针法（第二篇会讲）实现 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度——但前提是先排序，而这一步本身就需要 $O(n \log n)$ 的时间开销。

模式：互补搜索#

碰到题目要求 “找满足某种关系的数对”，先想想能不能换个思路：对每个 x，检查之前是否见过某个 y，使得 f(x, y) 成立？如果能，那大概率就是哈希表的用武之地了。

三、字母异位词分组：规范化键模式#

LeetCode 49. 给定一个字符串数组，将字母异位词归类到一起。

1
2

输入：["eat", "tea", "tan", "ate", "nat", "bat"]
输出：[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

字母异位词的核心特征是 字符组成相同但排列不同。解题的关键在于找到一种“规范化”的表示方法，让所有异位词共享同一个键。

方案一：用排序后的字符串当键#

最直接的规范化方式：把字符排个序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from collections import defaultdict
from typing import List

def group_anagrams(strs: List[str]) -> List[List[str]]:
    """时间 O(n · k log k)，n = len(strs)，k = 最长字符串长度。"""
    groups: dict[str, list[str]] = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))   # "eat", "tea", "ate" 都排成 "aet"
        groups[key].append(s)
    return list(groups.values())

简单、通用，对任何字符集都能用。开销主要在排序：每个字符串 $O(k \log k)$ 。

方案二：用字符计数作为键#

如果字符集比较小，比如全是小写字母（总共 26 个），可以直接统计每个字母的出现次数。这样做的时间复杂度是 $O(k)$ ，还能省掉排序的开销：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from collections import defaultdict
from typing import List

def group_anagrams(strs: List[str]) -> List[List[str]]:
    """用 26 维计数数组当键，时间复杂度 O(n · k)。"""
    groups: dict[tuple[int, ...], list[str]] = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord("a")] += 1
        # list 本身不可哈希，转成 tuple 就能当字典键了。
        groups[tuple(count)].append(s)
    return list(groups.values())

这里有个容易踩坑的地方：字典的键必须 不可变且可哈希。直接用 list 会报错，换成 tuple 就没问题了。

模式：规范化表示#

如果题目要求“把某种对称性下相等的东西分组、查找或计数”，关键问题就是 “这个等价类的最小公共表示是什么？” 找到这个表示，直接用它作为哈希键即可。

这种思路的核心是找到一个能唯一标识等价类的表示。无论是排序、计数还是差值计算，目标都是让同一个等价类的所有成员映射到同一个键上。选对了键，问题就解决了一大半。

四、无重复字符的最长子串：滑动窗口 + 哈希表#

LeetCode 3. 给定一个字符串 s，找出其中不包含重复字符的最长子串的长度。

1
2

输入：s = "abcabcbb"
输出：3            # 子串 "abc"

这道题是哈希表和滑动窗口配合的经典案例。我们维护一个窗口 [left, right]，右边界 right 每次向右扩展一个字符。如果新加入的字符会导致窗口内出现重复字符，就从左侧收缩窗口，直到窗口重新合法为止。

哈希表的作用是记录每个字符最近一次出现的位置。遇到重复字符时，我们可以直接将左边界 left 跳到重复字符的下一个位置，而不是一步步移动。这就是优化的关键。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def length_of_longest_substring(s: str) -> int:
    """记录每个字符的最近下标。时间复杂度 O(n)，空间复杂度 O(min(n, |Σ|))。"""
    last_seen: dict[str, int] = {}
    left = 0
    best = 0

    for right, ch in enumerate(s):
        # 如果 ch 在当前窗口内已经出现过，则需要收缩左边界。
        # 使用 max 是为了忽略窗口外的历史记录。
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1

        last_seen[ch] = right
        best = max(best, right - left + 1)

    return best

以下是 "abcabcbb" 的执行过程：

这段代码的核心在于如何高效地处理重复字符。通过哈希表记录字符的最新位置，我们避免了逐个移动左边界的操作，从而将时间复杂度降到线性级别。

模式：变长窗口 + 哈希状态#

如果题目要求找“满足某种条件的 最长或最短 子串/子数组”，并且加入或移除一个元素时，窗口状态可以在 $O(1)$ 时间内更新，那么就可以直接套用这个模板：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

left = 0
state = {}                       # 跟踪窗口状态的任意数据结构

for right, x in enumerate(arr):
    add(x, state)                # 扩展窗口

    while not valid(state):      # 窗口不合法时收缩，直到恢复合法
        remove(arr[left], state)
        left += 1

    update_answer(left, right)   # 更新最终答案

后续会遇到的类似问题包括：最小覆盖子串（LeetCode 76）、最多包含 K 个不同字符的最长子串（LeetCode 340）、字符串的排列（LeetCode 567）。

五、前 K 个高频元素：频率统计 + 桶排序#

LeetCode 347. 给整数数组 nums 和整数 k，返回出现频率前 k 高的元素。

1
2

输入：nums = [1, 1, 1, 2, 2, 3], k = 2
输出：[1, 2]

第一步显然是用哈希表（或 Counter）统计频率。第二步才是设计的关键：怎么挑出 top k？

方案一：用堆实现（$O(n \log k)$ ）#

把每对 (count, value) 插入一个大小为 k 的小顶堆，保持堆的规模不超过 k。这种方法适合处理数据量大但 k 较小的情况。

1
2
3
4
5
6
7
8
9

import heapq
from collections import Counter
from typing import List

def top_k_frequent(nums: List[int], k: int) -> List[int]:
    """时间复杂度 O(n log k)，空间复杂度 O(n)。"""
    freq = Counter(nums)
    # most_common 内部已经实现了基于堆的操作。
    return [val for val, _ in freq.most_common(k)]

Counter.most_common 底层直接调用了堆操作，代码简洁且高效，日常使用完全够用。

方案二：桶排序（$O(n)$ ）#

频率的上限是 $n$ ，所以可以反过来操作——用频率作为桶的下标，把每个值放到对应的桶里，然后从高频到低频依次读取：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from collections import Counter
from typing import List

def top_k_frequent(nums: List[int], k: int) -> List[int]:
    """按频率进行桶排序。时间复杂度 O(n)，空间复杂度 O(n)。"""
    freq = Counter(nums)

    # buckets[f] 存放所有出现频率为 f 的值。
    # 一个值最多出现 n 次，因此需要 n+1 个桶（索引从 0 到 n）。
    buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
    for value, count in freq.items():
        buckets[count].append(value)

    # 从高频率桶开始往下扫描。
    result: list[int] = []
    for f in range(len(buckets) - 1, 0, -1):
        for value in buckets[f]:
            result.append(value)
            if len(result) == k:
                return result
    return result

这是经典的“频率有界，直接用频率当索引”的技巧。算法的时间复杂度严格是 $O(n)$ ，没有 $\log$ 因子；类似的方法还会出现在“按频率排序字符”（LeetCode 451）等问题中。

模式：频率统计#

用 Python 写频率统计，有三个惯用法，写多了基本就成条件反射：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from collections import Counter, defaultdict

# 1. 一行搞定计数。
freq = Counter(nums)                       # {1: 3, 2: 2, 3: 1}

# 2. 分组时自动初始化桶。
groups = defaultdict(list)
for x in items:
    groups[key_of(x)].append(x)

# 3. 一行判断两个多重集是否相等。
def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

频率映射的用途非常广泛：异位词判定、找多数元素、找第一个唯一字符、按频率排序、 Top-K，以及各种“某个值出现了几次”的问题，几乎都能靠它解决。

六、常见陷阱#

面试中哈希表相关的 bug，几乎都逃不出这几条：

• 先插入再检查。两数之和问题里，必须先查补数是否存在，再插入当前值。否则可能会把一个数跟自己配对。
• 键不可哈希。 list、 set 和 dict 不能直接当字典的键。需要用 tuple(...) 或 frozenset(...) 转一下。
• 插入后修改键。如果用作键的对象内容被改动，它的哈希值就变了，原来的条目可能再也找不到了。记住：键要当作不可变对象处理。
• 滥用字典代替集合。seen[x] = True 这种写法比直接用 seen.add(x) 多浪费 30%–40% 的内存。
• 边遍历边修改。在迭代字典时增删键会触发 RuntimeError。真要改的话，先拷一份数据，比如用 list(d.items())。
• 依赖键的顺序。虽然 Python 3.7+ 保留了插入顺序，但别把算法逻辑建立在键的顺序上，这不是哈希表的设计初衷。

七、面试前的自检清单#

碰到一道题，觉得哈希表能派上用场时，动笔之前先在脑子里过一遍这些问题：

• 键选什么？ 是原值、排序后的形式、计数元组，还是前缀和？
• 值存什么？ 是下标、计数、下标列表，还是布尔标志？
• 用 set 还是 map？ 如果只关心元素是否存在， set 更轻便。
• 答案从哪来？ 是扫描过程中直接命中，还是最后再遍历一遍哈希表？
• 边界情况有哪些？ 比如空输入、单元素、全重复、全唯一、包含负数。

面试时口头表达可以这样说：

“暴力解法是 $O(n^2)$ ，因为每个元素都要和其他所有元素逐一比较。我可以通过一边扫描一边维护一个 <key> → <value> 的哈希表，把每次查找降到 $O(1)$ 。总时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。”

八、为什么面试总爱考哈希表#

两个原因，都很实在：

1. 哈希表能把 $O(n^2)$ 直接压成 $O(n)$ 。 这是“选对数据结构，算法就简单了”最经典的例子，也是算法面试的核心考点之一。只要你能发现内层循环在找的东西，外层循环其实已经知道了，那哈希表就是答案。
2. 真实世界的后端代码里到处都是它。 请求处理器写 users[user_id] 是哈希查找；流处理去重用的是 seen.add(...)；数据库前面的缓存本质也是哈希表。面试官喜欢出这类题是因为它的实用性最强，学会了就能直接用。

题面里的关键词：“找出满足条件的对/三元组/组合”、“之前有没有出现过”、“统计出现次数”——看到这些，基本就是在暗示你用哈希表了。

九、生产环境中的实际应用#

结合我自己的开发经验，分享三个和本文内容直接对应的场景：

• 两数之和 / 配对查找： 比如两边系统导出的文件需要对账： A 文件某一行应该匹配 B 文件中满足互补条件的那一行。先用小文件构建一个 dict，再扫描大文件即可完成匹配。复杂度从 O(a * b) 降到 O(a + b)。这个方法在数据量从小到大（几千行到几亿行）时都能高效工作。
• 按排序字符串分组： 商品 SKU 去重问题中，比如 "red,large,cotton" 和 "large,cotton,red" 实际上是同一个 SKU。解决方案是将属性排序后转为元组，即 tuple(sorted(...))，然后作为字典的 key 使用。
• 前缀和哈希解决“子数组和等于 K”。 这在时序数据分析中很常见，比如“找出所有营收正好等于 $X 的 5 分钟窗口”。这套技巧适用于任何可逆的聚合操作（如求和、异或、计数）。但如果是不可逆的操作（如最大值、最小值），就需要换其他数据结构。

面试题像是一个沙盒，而生产环境的需求通常会叠加流式处理、数据淘汰、并发控制等复杂性，但核心算法逻辑是一模一样的。

十、用边界用例自查#

拿 Two Sum 来说 —— 这道题是哈希表入门的经典题目，下面这些测试用例能帮你发现大部分实现问题：

1
2
3
4
5
6

two_sum([], 0)              # 空数组输入 —— 至少不能崩溃
two_sum([3], 3)             # 只有一个元素，无法配对 —— 返回空列表
two_sum([3, 3], 6)          # 两个相同值正好凑成目标值
two_sum([1, 2, 3], 7)       # 没有解的情况
two_sum([-1, -2, -3], -5)   # 负数元素的处理
two_sum([0, 0], 0)          # 零值输入 —— `if num` 的写法容易在这里出错

其中 [3, 3] 是最容易踩坑的用例。如果一边遍历一边直接存入 seen[num] = i，顺序不对就会把下标 0 和自己配对。解决方法很简单：先查再存。

1
2
3
4
5
6
7

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:        # 先查补数是否存在
            return [seen[target - x], i]
        seen[x] = i                   # 再存当前值
    return []

就这两行代码，顺序对了就能过。这道题之所以被频繁用来考察，全在这两行的细节上。

十一、接下来练什么#

等你把这四道模板题练到条件反射般熟悉后，可以按下面的难度梯度继续提升：

• 简单级别
  存在重复元素（217）、有效的字母异位词（242）、两个数组的交集（349）。
  这些题目适合巩固基础，确保对哈希表的基本操作滚瓜烂熟。

• 中等级别
  和为 K 的子数组（560）、最长连续序列（128）、四数相加 II （454）、常数时间插入删除取随机（380）。
  这些题目开始引入更多复杂性，比如前缀和技巧、频率统计、以及哈希表与其他数据结构的结合。

• 困难级别
  缺失的第一个正数（41——巧妙地把输入数组本身当哈希表用）、串联所有单词的子串（30）、至多含 K 个不同字符的最长子串（340）。
  这些题目不仅考验哈希表的应用能力，还要求你灵活处理边界条件和优化空间复杂度。

下一篇 双指针 会带你探索另一个方向：当输入有序（或者可以排序时），双指针能在 $O(n)$ 时间内实现只用 $O(1)$ 额外空间的效果，与哈希表旗鼓相当。真正的难点在于 如何根据问题特性选择合适的方法——我们下一篇见分晓。