哈希表

哈希表的核心“超能力”

• 核心能力：在平均情况下，以 O(1) 的时间复杂度完成插入、删除、查找操作。
• 本质：它提供了一种近乎即时的方式来回答“我见过这个东西吗？”或者“与这个东西关联的信息是什么？”

基于这个超能力，我们发展出了以下几种核心的算法思维模式：

模式一：空间换时间 —— “以存代查，建立备忘录”

这是哈希表最经典、最直接的应用。当你的算法中出现了嵌套循环，尤其是内层循环是在寻找一个“配对”或“补数”时，你就要立刻想到：我可以用哈希表替代内层循环吗？

• 核心思想：将一个O(n)的线性查找，降维成一个O(1)的哈希查找。

• 典型例题：两数之和 (Two Sum)

  • 慢速思路 (O(n²))：对于每个数字 x，都向后遍历整个数组，寻找是否存在 target - x。
  • 哈希表思路 (O(n))：
    1. 创建一个哈希表作为“备忘录”。
    2. 遍历数组，对于每个数字 x，不去遍历，而是直接问备忘录：“target - x 你见过吗？”
    3. 如果见过，问题解决。
    4. 如果没见过，就把当前的 x 和它的索引存入“备忘录”，以备后来的数字查询。

• 思维触发点：当你需要为一个元素 x 快速找到它的“另一半” y 时，就用哈希表。

模式二：分组与归类 —— “找到共同特征，进行映射”

当问题需要你将一系列元素按照某种“内在特征”进行分组时，哈希表是完美的工具。

• 核心思想：为具有相同特征的一类元素，计算出一个独一无二的、规范化的“签名”（Canonical Key），然后将这个签名作为键，将元素本身存入值（通常是一个列表）。

• 典型例题：字母异位词分组 (Group Anagrams)

  • 内在特征：两个词互为字母异位词，意味着它们包含的字母及数量完全相同。
  • “签名”计算：对字符串进行排序。"eat", "tea", "ate" 的签名都是 "aet"。
  • 哈希表思路 (O(n*k log k)) (k为字符串平均长度):
    1. 创建一个 defaultdict(list) 的哈希表。
    2. 遍历每个字符串，计算它的“签名”（排序后的字符串）。
    3. 用这个签名作为键，将原字符串 append 到对应的列表中。mp["aet"].append("eat")。

• 思维触发点：当你需要将“看起来不同，但本质相同”的东西归为一类时，思考如何为它们定义一个统一的“身份证”（签名），并用哈希表进行归类。

模式三：快速判断存在性 —— “利用集合优化起点判断”

这个模式是“空间换时间”的延伸，但更侧重于利用哈希集合（Set，可以看作只有键的哈希表）来优化逻辑，避免重复计算。

• 核心思想：先将所有元素放入一个哈希集合，然后利用其O(1)的查询特性，来判断一个元素是否满足某种“特殊条件”（例如，是否是序列的起点），从而避免大量不必要的计算。

• 典型例题：最长连续序列 (Longest Consecutive Sequence)

  • 朴素思路 (O(n log n))：先排序，再遍历。简单直观，但排序本身耗时。
  • 哈希表思路 (O(n))：
    1. 将所有数字放入一个哈希集合 num_set。目的：为了能 O(1) 地回答“数字 k 是否存在？”
    2. 遍历每个数字 num，进行一个关键判断：if num - 1 not in num_set:。
    3. 这个判断的目的：只对一个连续序列的最小的那个数（起点）进行处理。对于 [1,2,3,4]，我们只对 1 进行详细的向后查找，而 2,3,4 都会因为 num-1 存在而被跳过。
    4. 这极大地减少了计算量，将一个看似O(n²)的嵌套循环，通过均摊分析，变为了O(n)。

• 思维触发点：当你的算法需要处理连续、相邻的元素关系，并且可能存在大量重复计算时，思考能否用哈希集合来快速判断“前驱”或“后继”是否存在，从而找到一个唯一的“起点”来开始计算。

总结：你的哈希表工具箱

下次遇到算法题，尤其是关于数组或字符串的，可以从以下几个角度思考哈希表能否帮你优化：

当你遇到...	你可以思考...	哈希表的作用
嵌套循环，尤其是内层在查找	能否用“备忘录”替代内层循环？	空间换时间，O(n)查找 -> O(1)查找
需要分组的问题	能否为每一组定义一个唯一的“签名”作为键？	分组与归类，map[签名].append(元素)
涉及大量“是否存在”的判断	能否先把数据存入哈希集合？	快速判断存在性，if x in my_set:
处理序列/连续性问题	能否用哈希集合判断元素的“前驱”是否存在，从而找到起点？	优化起点判断，if x-1 not in my_set:

---

字典常见操作¶

字典（dict）是 Python 中最核心的数据结构之一，本质是基于哈希表实现的键值映射结构。特点是：查找、插入、删除平均时间复杂度为 O(1)，键必须是不可变类型（如 int、str、tuple）。

下面按使用场景系统总结常见操作。

一、创建字典

1）字面量方式（最常用）

d = {"a": 1, "b": 2}

2）dict() 构造函数

d = dict(a=1, b=2)             # 仅限字符串键
d = dict([("a", 1), ("b", 2)]) # 可迭代对象

3）空字典

d = {}
d = dict()

注意：{} 是空字典，不是集合。空集合必须用 set()。

二、访问与查询

1）通过 key 访问

value = d["a"]

若 key 不存在会抛出 KeyError。

2）安全访问：get()

value = d.get("a")          # 不存在返回 None
value = d.get("a", 0)       # 指定默认值

推荐在不确定 key 是否存在时使用 get。

3）判断 key 是否存在

if "a" in d:

底层是哈希查找，时间复杂度 O(1)。

三、增删改操作

1）新增或修改

d["c"] = 3      # 若存在则覆盖

2）删除元素

del d["a"]               # 不存在会报错
value = d.pop("a")       # 删除并返回值
value = d.pop("a", 0)    # 不存在返回默认值

3）删除最后一个元素（Python 3.7+ 有序）

d.popitem()

4）清空字典

d.clear()

四、遍历字典

1）遍历 key（默认方式）

for key in d:

2）遍历 value

for value in d.values():

3）遍历键值对（最常用）

for key, value in d.items():

五、常用高级操作

1）更新字典

d.update({"a": 10, "d": 4})

等价于批量赋值。

2）合并字典（Python 3.9+）

d3 = d1 | d2

或

d1.update(d2)

3）字典推导式

d = {x: x*x for x in range(5)}

常用于构造映射表。

六、collections.defaultdict

defaultdict 是 dict 的子类。 核心差异在于：当访问不存在的 key 时，不会抛出 KeyError，而是自动创建一个默认值。

from collections import defaultdict
d = defaultdict(int)
d["a"] += 1

比 setdefault 更简洁，推荐用于：

• 计数统计
• 分组聚类
• 构图邻接表

七、排序

按 key 排序：

sorted(d.items(), key=lambda x: x[0])

按 value 排序：

sorted(d.items(), key=lambda x: x[1])

注意：sorted 返回的是列表，不是字典。

八、时间复杂度与底层原理

dict 底层是哈希表：

• 查询：O(1)
• 插入：O(1)
• 删除：O(1)

极端情况下（哈希冲突严重）退化为 O(n)，但实际几乎不会出现。

Python 3.7+ 字典保持插入顺序，这是语言规范保证的。

十、关键本质总结

字典的核心思想是： 用哈希函数将 key 映射到内存地址，从而实现常数级查找。

使用时牢记三点：

1）key 必须是不可变类型 2）查询优先用 get 防止异常 3）计数与分组优先考虑 defaultdict

时间复杂度： 查找 / 插入 / 删除平均 O(1)

空间复杂度： O(n)，存储 n 个键值对

---

集合常见操作¶

集合（set）是基于哈希表实现的无序、不重复元素容器。核心用途只有两个： 1）快速判重 2）集合运算

其本质是：用哈希结构实现 O(1) 级别的查找。

一、创建集合

s = set()            # 空集合
s = {1, 2, 3}        # 推荐写法
s = set([1, 2, 3])   # 可迭代对象构造

二、基本增删查

1）添加元素

s.add(5)

2）删除元素

s.remove(5)    # 不存在会报错
s.discard(5)   # 不存在不会报错（推荐）

3）弹出元素（随机）

s.pop()

4）清空

s.clear()

5）判断是否存在

if 5 in s:

时间复杂度：平均 O(1)

三、集合运算（核心重点）

假设：

a = {1,2,3}
b = {2,3,4}

1）交集（共同元素）

a & b
a.intersection(b)

2）并集（全部元素）

a | b
a.union(b)

3）差集（a 有，b 没有）

a - b
a.difference(b)

4）对称差集（不同时存在的元素）

a ^ b
a.symmetric_difference(b)

四、常见面试使用场景

1）去重

nums = list(set(nums))

2）快速查重

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

3）滑动窗口去重

4）图搜索 visited 标记

五、不可变集合 frozenset

fs = frozenset([1,2,3])

特点：

• 不可修改
• 可以作为字典的 key
• 可以作为集合元素

六、复杂度总结

底层结构：哈希表

• 查找：O(1)
• 插入：O(1)
• 删除：O(1)
• 空间：O(n)

七、本质总结

集合只做三件事：

1）保证元素唯一 2）提供 O(1) 存在性判断 3）支持数学集合运算

使用原则：

• 只关心“有没有” → 用 set
• 需要计数 → 用 dict
• 需要分组 → 用 defaultdict

集合的核心价值在于：用空间换时间，实现常数级判重效率。

---

1.两数之和¶

给定一个数组找出两个数和为目标值target的数组下标

In [22]:

"""类名 (Class Name): 应使用大驼峰命名法 (PascalCase)
函数/方法名 (Function/Method Name): 应使用蛇形命名法 (snake_case)，即所有字母小写并用下划线分隔"""
class Solution:
    def sum_two(self, target, nums):
        """哈希表（词典）能直接查询某个元素，相比于列表的挨个遍历"""
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target-num], i]
            hashtable[num] = i
        return []

test_nums = [1, 2, 5, 10]
target = 11
sumtwo = Solution()
a = sumtwo.sum_two(target, test_nums)
print(a)

"""类名 (Class Name): 应使用大驼峰命名法 (PascalCase) 函数/方法名 (Function/Method Name): 应使用蛇形命名法 (snake_case)，即所有字母小写并用下划线分隔""" class Solution: def sum_two(self, target, nums): """哈希表（词典）能直接查询某个元素，相比于列表的挨个遍历""" hashtable = dict() for i, num in enumerate(nums): if target - num in hashtable: return [hashtable[target-num], i] hashtable[num] = i return [] test_nums = [1, 2, 5, 10] target = 11 sumtwo = Solution() a = sumtwo.sum_two(target, test_nums) print(a)

[0, 3]

直接返回组原值，而不是下标

In [8]:

def twosum(target, nums):
    hashtable = set(nums)
    for i in nums:
        if target - i in hashtable:
            return [target - i, i]
    return []
test_nums = [1, 2, 5, 10]
target = 11
output = twosum(target, test_nums)
output

def twosum(target, nums): hashtable = set(nums) for i in nums: if target - i in hashtable: return [target - i, i] return [] test_nums = [1, 2, 5, 10] target = 11 output = twosum(target, test_nums) output

Out[8]:

[10, 1]

49.字母异或位分组¶

给定一个数组，将字母异位词组合在一起输出

sorted() 是 Python 中最常用的排序函数之一。在算法题、数据处理和工程代码中都非常常见。核心理解只有两点：排序对象与排序依据（key）。

1. 基本用法

语法：

sorted(iterable, key=None, reverse=False)

含义：

• iterable：要排序的可迭代对象（list、str、tuple等）
• key：指定排序依据
• reverse=True：降序排序

示例：

nums = [3,1,4,2]
print(sorted(nums))

结果：

[1,2,3,4]

特点：

• 返回 新的排序结果
• 不会改变原数据

2. 字符串排序（算法题最常见）

字符串会被当作 字符序列 进行排序。

s = "eat"
print(sorted(s))

结果：

['a','e','t']

如果需要字符串：

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

在 LeetCode 49 Group Anagrams 中就是这样生成 key。

3. key 的本质

key 表示 排序依据函数。

排序过程可以理解为：

元素  → key函数  → 得到排序依据 → 按依据排序

形式：

sorted(data, key=lambda x: 排序依据)

lambda x 表示每次取一个元素 x。

4. key=lambda x: 常见用法

① 按元素本身排序（基本不用写）

sorted(nums, key=lambda x: x)

等价于

sorted(nums)

② 按某个位置排序（最常见）

例如：

data = [(1,3),(2,1),(4,2)]

按第二个元素排序：

sorted(data, key=lambda x: x[1])

结果：

[(2,1),(4,2),(1,3)]

解释：

x = (1,3)
x[1] = 3

排序依据是第二个值。

算法题中非常常见：

intervals.sort(key=lambda x: x[1])

表示 按区间右端点排序。

③ 按长度排序

words = ["apple","hi","banana"]

sorted(words, key=lambda x: len(x))

结果：

['hi','apple','banana']

排序依据：

len(x)

④ 多关键字排序（非常重要）

data = [("Tom",20),("Jack",20),("Lucy",18)]

先按年龄，再按名字：

sorted(data, key=lambda x: (x[1], x[0]))

排序依据：

(age, name)

结果：

[('Lucy',18),('Jack',20),('Tom',20)]

⑤ 字典对象排序

data = [
    {"name":"Tom","age":20},
    {"name":"Lucy","age":18}
]

按 age 排序：

sorted(data, key=lambda x: x["age"])

1. sorted vs sort

	sorted	sort
类型	函数	list方法
是否返回新对象	是	否
是否修改原列表	否	是

sorted(nums)
nums.sort()

算法题中两者都常见。

1. 算法题中最常见的三种写法

1 按元素排序

sorted(nums)

2 按某个位置排序

sorted(data, key=lambda x: x[1])

3 多关键字排序

sorted(data, key=lambda x: (x[1], x[0]))

1. 一句话理解 lambda

lambda x: 表示对每个元素 x 计算一个排序依据

例如：

lambda x: x[1]

意思就是：

按照每个元素的第二个值排序

In [ ]:

import collections
from typing import List

class Solution:
    """
    该类用于将字母异位词组合在一起。
    """
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        # 创建一个默认值为列表的字典,相比于dict，能直接加入不存在的键
        mp = collections.defaultdict(list)

        # 遍历输入列表中的每个字符串
        for st in strs:
            # 将字符串排序后作为键
            key = "".join(sorted(st))
            print(f"原来字符串为{st}\n sorted(st)后的字符串为{sorted(st)}\n key值为{key}")
            """
            sorted() 函数的返回值永远是一个列表,['a', 'e', 't']
            .join()将一个可迭代对象中的所有元素连接成一个单一的字符串
            空字符串 ""，引号中的字符表示在连接处加入相应的字符，这里表示无缝连接
            """
            # 将原字符串添加到对应键的列表中
            mp[key].append(st)
        
        # 返回字典中所有的值（即分组后的列表）,一定要将dict_values转成list。
        return list(mp.values())

# --- 以下是调用函数的示例 ---

# 1. 创建一个Solution类的实例
solver = Solution()

# 2. 准备一组用于测试的字符串列表
input_strings = ["eat", "tea", "tan", "ate", "nat", "bat"]

# 3. 调用实例的 groupAnagrams 方法，并传入测试数据
result = solver.groupAnagrams(input_strings)

# 4. 打印输入和输出结果
print(f"输入 (Input): {input_strings}")
print(f"输出 (Output): {result}")

import collections from typing import List class Solution: """ 该类用于将字母异位词组合在一起。 """ def groupAnagrams(self, strs: List[str]) -> List[List[str]]: # 创建一个默认值为列表的字典,相比于dict，能直接加入不存在的键 mp = collections.defaultdict(list) # 遍历输入列表中的每个字符串 for st in strs: # 将字符串排序后作为键 key = "".join(sorted(st)) print(f"原来字符串为{st}\n sorted(st)后的字符串为{sorted(st)}\n key值为{key}") """ sorted() 函数的返回值永远是一个列表,['a', 'e', 't'] .join()将一个可迭代对象中的所有元素连接成一个单一的字符串 空字符串 ""，引号中的字符表示在连接处加入相应的字符，这里表示无缝连接 """ # 将原字符串添加到对应键的列表中 mp[key].append(st) # 返回字典中所有的值（即分组后的列表）,一定要将dict_values转成list。 return list(mp.values()) # --- 以下是调用函数的示例 --- # 1. 创建一个Solution类的实例 solver = Solution() # 2. 准备一组用于测试的字符串列表 input_strings = ["eat", "tea", "tan", "ate", "nat", "bat"] # 3. 调用实例的 groupAnagrams 方法，并传入测试数据 result = solver.groupAnagrams(input_strings) # 4. 打印输入和输出结果 print(f"输入 (Input): {input_strings}") print(f"输出 (Output): {result}")

原来字符串为eat
 sorted(st)后的字符串为['a', 'e', 't']
 key值为aet
原来字符串为tea
 sorted(st)后的字符串为['a', 'e', 't']
 key值为aet
原来字符串为tan
 sorted(st)后的字符串为['a', 'n', 't']
 key值为ant
原来字符串为ate
 sorted(st)后的字符串为['a', 'e', 't']
 key值为aet
原来字符串为nat
 sorted(st)后的字符串为['a', 'n', 't']
 key值为ant
原来字符串为bat
 sorted(st)后的字符串为['a', 'b', 't']
 key值为abt
输入 (Input): ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
输出 (Output): [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

In [1]:

import collections
from typing import List
class Solution:
    def test(self, strs):
        hashdict = collections.defaultdict(list)
        for i in strs:
            key = ''.join(sorted(i))
            hashdict[key].append(i)
        print(hashdict.values())
        return list(hashdict.values())
strs = ['aet', 'ate', 'eat', 'app', 'ppa']
jw = Solution()
a = jw.test(strs)
print(a)

import collections from typing import List class Solution: def test(self, strs): hashdict = collections.defaultdict(list) for i in strs: key = ''.join(sorted(i)) hashdict[key].append(i) print(hashdict.values()) return list(hashdict.values()) strs = ['aet', 'ate', 'eat', 'app', 'ppa'] jw = Solution() a = jw.test(strs) print(a)

dict_values([['aet', 'ate', 'eat'], ['app', 'ppa']])
[['aet', 'ate', 'eat'], ['app', 'ppa']]

128.最长连续序列¶

给定一个数组，找到连续的最长序列长度

核心思路

凡是可以查找的，都用哈希表

1.确定起点(通过-1在哈希表查找确定起点)

2.通过不断+1查找，确定长度

In [25]:

from typing import List
class Solution:
    """
    (1)确定连续序列的起点
    (2)确定该序列的最大长度
    """
    def longestConsecutive(self, nums: List[int]) -> int:
        max_length = 0
        nums_set = set(nums)
        for i in nums_set:
            # 确定连续序列的起点：如果i-1不在集合中，说明i是一个连续序列的起点
            if i-1 not in nums_set:
                cur_num = i
                cur_length = 1
                # 确定该序列的最大长度：不断检查cur_num+1是否在集合中，如果在，说明序列继续，更新cur_num和cur_length
                while cur_num + 1 in nums_set:
                    cur_length += 1
                    cur_num += 1
                max_length = max(max_length, cur_length)
                
        return max_length
# --- 示例调用 ---
solver = Solution()
test_nums = [100, 4, 200, 1, 3, 2]
print(f"输入: {test_nums}, 最长连续序列长度: {solver.longestConsecutive(test_nums)}") # 应为 4 (1,2,3,4)

test_nums_with_duplicates = [1, 2, 0, 1]
print(f"输入: {test_nums_with_duplicates}, 最长连续序列长度: {solver.longestConsecutive(test_nums_with_duplicates)}") # 应为 3 (0,1,2)

from typing import List class Solution: """ (1)确定连续序列的起点 (2)确定该序列的最大长度 """ def longestConsecutive(self, nums: List[int]) -> int: max_length = 0 nums_set = set(nums) for i in nums_set: # 确定连续序列的起点：如果i-1不在集合中，说明i是一个连续序列的起点 if i-1 not in nums_set: cur_num = i cur_length = 1 # 确定该序列的最大长度：不断检查cur_num+1是否在集合中，如果在，说明序列继续，更新cur_num和cur_length while cur_num + 1 in nums_set: cur_length += 1 cur_num += 1 max_length = max(max_length, cur_length) return max_length # --- 示例调用 --- solver = Solution() test_nums = [100, 4, 200, 1, 3, 2] print(f"输入: {test_nums}, 最长连续序列长度: {solver.longestConsecutive(test_nums)}") # 应为 4 (1,2,3,4) test_nums_with_duplicates = [1, 2, 0, 1] print(f"输入: {test_nums_with_duplicates}, 最长连续序列长度: {solver.longestConsecutive(test_nums_with_duplicates)}") # 应为 3 (0,1,2)

输入: [100, 4, 200, 1, 3, 2], 最长连续序列长度: 4
输入: [1, 2, 0, 1], 最长连续序列长度: 3

刷题错误：

1.必须注意 cur_start = i、cur_start += 1

2.遍历集合的时候，不能删除集合中的元素

In [26]:

from typing import List
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        max_len = 0
        hashset = set(nums)
        for i in hashset:
            if i - 1 not in hashset:
                cur_len = 1
                cur_start = i
                while cur_start + 1 in hashset:
                    cur_start += 1
                    cur_len += 1
                max_len = max(max_len, cur_len)
                
        return max_len
nums = [1, 100, 3, 10, 2]
jw = Solution()
max_len = jw.longestConsecutive(nums)
max_len

from typing import List class Solution: def longestConsecutive(self, nums: List[int]) -> int: max_len = 0 hashset = set(nums) for i in hashset: if i - 1 not in hashset: cur_len = 1 cur_start = i while cur_start + 1 in hashset: cur_start += 1 cur_len += 1 max_len = max(max_len, cur_len) return max_len nums = [1, 100, 3, 10, 2] jw = Solution() max_len = jw.longestConsecutive(nums) max_len

Out[26]:

3