🧮 01-数据结构与算法 · 主题 1:数组与哈希表¶
秋招算法第一课。数组是内存布局的基石,哈希表是「空间换时间」的核心武器。 本 notebook 目标:看懂原理 → 能手写哈希表 → 吃透 9 道高频题 → 通过 25 道自测。
学习路线¶
- §2 数组:操作与复杂度公式
- §3 哈希表:原理、冲突处理、均摊分析(含手写实现)
- §4–§6 高频题精讲:两数之和 / 三数之和 / 移动零 / 轮转数组 / 合并区间 / 最长连续序列 / 除自身以外数组的乘积 / 和为 K 的子数组 / 多数元素
- §7 复杂度总表
- §8 常见 bug 与边界
- §9 面试追问与扩展
- §10 自测清单(L1/L2/L3)
运行环境:Python 3.8+,无第三方依赖,从上到下运行所有 cell 即可。
核心概念¶
(a) 🗂️ 数组与哈希表:原理、复杂度与 9 道高频题¶
数组是内存布局的基石,哈希表是"空间换时间"的核心武器。本 notebook 讲透两者原理,精讲两数/三数之和等 9 道高频题,并背熟复杂度总表。
flowchart TB
N1["🧮 数组与哈希:秋招地基"] --> N2["数组操作与复杂度"]
N2 --> N3["Python list 实用细节"]
N1 --> N4["哈希表原理:空间换时间"]
N4 --> N5["冲突处理与均摊分析"]
N2 --> N6["题 A:两数/三数之和(哈希查表)"]
N2 --> N7["题 B:原地操作三连"]
N5 --> N8["题 C:哈希五题套路"]
N6 --> N9["复杂度总表与自测"]
N7 --> N9
N8 --> N9
- N1 · 数组与哈希:秋招地基:数组和哈希表几乎出现在每一场面试里:数组是大量题目的载体,哈希表能把 O(n) 查找降到 O(1),是"空间换时间"的典范。
- N2 · 数组操作与复杂度:数组按索引随机访问是 O(1),但因为要挪动元素,中间插入/删除是 O(n)。记住这两条,就能快速判断很多题的复杂度上限。
- N3 · Python list 实用细节:Python 的 list 本质是动态数组:支持负索引、切片、原地修改;扩容时翻倍拷贝,均摊下来仍是 O(1) 的追加。这些细节是手写题的基础。
- N4 · 哈希表原理:哈希表通过哈希函数把任意 key 映射到数组下标,实现 O(1) 的查找/插入/删除;它"记住"了见过的元素,正是两数之和这类题的关键。
- N5 · 冲突处理与均摊分析:不同 key 可能映射到同一位置(冲突),常用链地址法/开放寻址解决;装载因子过高就扩容,翻倍扩容摊到每次操作上仍是 O(1)——这就是均摊分析。
- N6 · 题 A:两数/三数之和:两数之和用"一边遍历一边查哈希";三数之和先排序再用双指针,去重是真正的考点,代表"哈希查表 + 双指针"两大类套路。
- N7 · 题 B:原地操作三连:移动零、轮转数组、合并区间都是"原地操作"套路:用指针重排、三次反转、排序后合并,考察对数组底层布局的理解。
- N8 · 题 C:哈希五题套路:每道题代表一类模板——前缀和(和为 K 的子数组)、Boyer-Moore 投票(多数元素)、原地哈希(缺失的第一个正数)等,背熟模板事半功倍。
- N9 · 复杂度总表与自测:最后用一张复杂度总表收尾(数组/list、dict/set、均摊分析),再用 L1/L2/L3 自测清单检验掌握程度。
§1 为什么数组与哈希是秋招地基¶
面试怎么考¶
- 数组:负索引、切片、原地操作、双指针配合——大量题的基础载体
- 哈希表:把 $O(n)$ 查找降到 $O(1)$,是「空间换时间」的典范,几乎每场面试必有 1 题
- 手撕题:手写哈希表 / LRU / 去重——考察你是否真正理解哈希原理
数据规模 → 复杂度(30 秒判断法)¶
拿到题先看输入规模 $n$:
| $n$ | 允许的复杂度 | 典型做法 |
|---|---|---|
| $n \le 20$ | $O(2^n)$ / $O(n!)$ | 暴力、回溯 |
| $n \le 10^3$ | $O(n^2)$ | 双循环 + 优化 |
| $n \le 10^5$ | $O(n \log n)$ | 排序、二分、堆 |
| $n \le 10^6+$ | $O(n)$ / $O(n \log n)$ | 一次扫描、哈希、排序 |
💡 判断口诀:1 秒约 $10^7$~$10^8$ 次基本操作,把复杂度代进 $n$,别超过这个量级。
心智模型¶
- 数组 = 一排编号的储物柜,知道编号直接开柜($O(1)$ 随机访问)
- 哈希表 = 带「标签」的储物间,把钥匙 hash 成柜号,冲突了就在柜里排队(链地址)或找下一个空柜(开放寻址)
§2 数组:操作与复杂度公式¶
2.1 随机访问 $O(1)$¶
数组在内存中连续存放,首地址为 $\text{base}$,元素大小 $s$ 字节:
$$\text{addr}(a_i) = \text{base} + i \times s$$
下标计算是一次乘法一次加法——常数时间,与 $n$ 无关。
2.2 插入 / 删除 $O(n)$¶
在第 $i$ 个位置插入需要把 $a_i \dots a_{n-1}$ 全部后移一位:
$$T_{insert}(i) = n - i \implies T_{insert} = O(n)$$
同理删除中间元素要前移。只有尾部操作(append / pop)是 $O(1)$(均摊,见 §7)。
2.3 Python 的 list 是什么¶
- Python
list是动态数组(不是链表):底层连续数组 + 自动扩容 - 扩容策略:容量翻倍,均摊 $O(1)$
- 切片
a[i:j]返回新列表,$O(k)$,$k = j - i$ - 负索引:
a[-1]等价于a[n-1],是语法糖,不是新数据结构
2.4 查找¶
- 按值查找:无序时 $O(n)$ 线性扫描;有序时 $O(\log n)$ 二分(主题 5 专讲)
- 哈希:$O(1)$——见 §3
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】演示 Python 数组(list,本质是动态数组)的核心操作及各自的复杂度:
# 随机访问 / 尾部追加 / 头部插入 / 切片 / 负索引 / 按值查找 / 列表推导式。
# 【算法思路】逐一执行每个基础操作并打印结果,注释标注复杂度,建立「操作 → 复杂度」的直觉:
# 知道下标直接取(O(1));头插要整体搬移(O(n));切片是新拷贝(O(k));
# 按值查找是线性扫描(O(n));推导式相当于 for + append。
# 【变量含义】arr=测试数组(先初始化 [1,2,3,4,5]);sub=切片 arr[1:4] 的新列表;
# squares=列表推导式生成的平方列表;其余为打印用的临时表达式。
# 【循环不变量】无显式循环;注意:切片与插入都不修改原 arr(list.insert 除外),
# 「切片返回新列表、原列表不变」是本单元反复强调的事实。
# 【关键边界】负索引 arr[-1] 等价于 arr[len(arr)-1];insert(0, …) 是 O(n) 的头部插入;
# 切片 arr[1:4] 左闭右开(含 1 不含 4);in / index 都是 O(n) 线性查找。
# 【复杂度】随机访问与尾部 append/pop 均摊 O(1);头/中间插入删除 O(n);
# 切片 O(k);按值查找 O(n)——这组结论是整个「数组与哈希」主题的复杂度地基。
# ════════════════════════════════════════════════════════════════════════
# 数组基础操作演示:随机访问 / 尾部操作 / 头部插入 / 切片 / 负索引 / 查找 / 推导式
arr = [1, 2, 3, 4, 5] # 初始化一个测试数组
print('随机访问 arr[2] =', arr[2]) # O(1)
# 尾部操作 O(1)
arr.append(6) # 尾部追加:动态数组均摊 O(1)
print('append 后:', arr)
# 头部插入 O(n):后续元素全部后移
arr.insert(0, 0) # 头部插入:后面所有元素都要挪一位,O(n)
print('insert(0) 后:', arr)
# 切片 O(k),返回新列表
sub = arr[1:4] # 切片返回新列表,长度 k = 3
print('arr[1:4] =', sub, ',原列表不变:', arr)
# 负索引语法糖
print('arr[-1] =', arr[-1], ' 等价于 arr[len(arr)-1] =', arr[len(arr) - 1])
# 按值查找:index() 线性扫描 O(n);in 判断存在性
print('arr.index(3) =', arr.index(3), ',7 in arr =', 7 in arr)
# 推导式构造
squares = [x * x for x in range(6)] # 列表推导式:生成 0~5 的平方
print('squares =', squares)
随机访问 arr[2] = 3 append 后: [1, 2, 3, 4, 5, 6] insert(0) 后: [0, 1, 2, 3, 4, 5, 6] arr[1:4] = [1, 2, 3] ,原列表不变: [0, 1, 2, 3, 4, 5, 6] arr[-1] = 6 等价于 arr[len(arr)-1] = 6 arr.index(3) = 3 ,7 in arr = False squares = [0, 1, 4, 9, 16, 25]
§3 哈希表:原理、冲突处理、均摊分析¶
3.1 哈希函数¶
把键 $k$ 映射到槽位:
$$h(k) = k \bmod m$$
要求:计算快、分布均匀、确定性。对字符串等复杂键,先用哈希算法把键变成整数再取模。
3.2 冲突与装载因子¶
不同键可能映射到同一槽(鸽巢原理:槽少于键数必冲突),两种主流处理:
链地址法(chaining):每个槽一条链表,冲突键挂到同一条链上。
开放寻址法(open addressing):冲突时按探测序列找下一个空位(线性探测 $h(k)+j$、二次探测、双重哈希)。
装载因子(load factor):
$$\alpha = \frac{n}{m} \quad (n=\text{元素数},\ m=\text{槽数})$$
均匀哈希假设下:
- 链地址:查找期望 $E = 1 + \frac{\alpha}{2}$,$\alpha$ 控制在 $\le 1$ 则常数小
- 开放寻址(线性探测):成功查找期望探测次数 $\approx \frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right)$,$\alpha > 0.7$ 后性能急剧恶化
⚠️ 为什么 Python dict 用开放寻址而不用链地址:缓存局部性好、无指针开销、内存紧凑;代价是删除要打「墓碑」(tombstone)标记。
3.3 resize 与均摊 $O(1)$¶
装载因子超阈值时翻倍扩容,重新哈希所有元素(单次 $O(n)$):
$$\text{均摊成本} = \frac{n \times O(1) + O(n) \text{(扩容)}}{n} = O(1)$$
和动态数组扩容同理:每次扩容翻倍,总搬移成本 $n + \frac{n}{2} + \frac{n}{4} + \dots < 2n = O(n)$,均摊到 $n$ 次插入就是 $O(1)$。
3.4 Python 的可哈希性¶
- 不可变对象(int / str / tuple / frozenset)可哈希;可变对象(list / dict / set)不可哈希
- 自定义类需同时实现
__hash__与__eq__,且相等的对象哈希值必须相同
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】用链地址法(chaining)从零手写哈希表 MyHashMap,实现 put / get / remove 三个核心操作,
# 并实现「装载因子超 0.75 触发翻倍扩容」的均摊 O(1) 策略;末尾用 20 个键值对实测。
# 【算法思路】底层是「槽位数组 + 桶内链表」:_hash 用 Python 内置 hash 对表长取模定位桶;
# put 先在桶内链表中查键(存在则更新、不存在则追加);
# size/capacity 超过 0.75 时翻倍扩容并重新哈希所有元素(表长变了,下标全变)。
# 【变量含义】capacity=表长(槽位数);table=槽位列表,每槽一条 (key, value) 链表;
# size=已存放的键值对总数;bucket=当前 key 所在的桶(链表);
# k / v=键值对;i=桶内遍历下标;old_table=扩容前的旧表;new_capacity=扩容后的表长。
# 【循环不变量】size 恒等于所有桶内键值对个数之和;桶内链表按插入顺序存放;
# 任一时刻装载因子 size/capacity ≤ 0.75(扩容后立即低于阈值)。
# 【关键边界】put 必须先查后插:键已存在则覆盖(不增加 size),不存在才 append 并 size+1;
# get 找不到返回默认值(默认 None);remove 键不存在返回 False;
# 扩容阈值判断 size > capacity * 0.75,翻倍后要遍历旧表全部桶逐个重哈希。
# 【复杂度】均匀哈希假设下:查找/插入/删除均摊 O(1)(装载因子被 0.75 限制住);
# 最坏 O(n)(哈希函数糟糕时单桶链长 O(n));单次扩容 O(n),均摊到每次操作仍是 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 链地址法手写哈希表:table 是「槽位 → 链表」结构,每个桶是一条 (key, value) 链表
# 关键设计:装载因子 size/capacity 超过 0.75 就翻倍扩容,保证操作均摊 O(1)
class MyHashMap:
'''链地址法手写哈希表:put / get / remove + 装载因子扩容'''
def __init__(self, capacity=8):
self.capacity = capacity # 槽位数量(表长)
self.table = [[] for _ in range(capacity)] # 每个槽位是一条空链表(桶)
self.size = 0 # 当前已存放的键值对个数
def _hash(self, key):
# Python 内置 hash:int 哈希为其自身,取模映射到槽位
return hash(key) % self.capacity # 哈希值对表长取模 → 确定桶下标
def put(self, key, value):
bucket = self.table[self._hash(key)] # 先定位 key 所在桶
for i, (k, v) in enumerate(bucket): # 遍历桶内链表,看该键是否已存在
if k == key:
bucket[i] = (key, value) # 键已存在:更新
return
bucket.append((key, value)) # 键不存在:新增
self.size += 1 # 元素数 +1
if self.size > self.capacity * 0.75: # 装载因子超 0.75 → 触发扩容
self._resize(self.capacity * 2) # 翻倍扩容并全部重新哈希
def get(self, key, default=None):
for k, v in self.table[self._hash(key)]: # 在对应桶的链表里线性查找
if k == key:
return v # 找到就返回值
return default # 没找到返回默认值(默认 None)
def remove(self, key):
bucket = self.table[self._hash(key)] # 定位桶
for i, (k, v) in enumerate(bucket): # 遍历桶内链表找该键
if k == key:
bucket.pop(i) # 找到:从链表中删除
self.size -= 1 # 元素数 -1
return True
return False # 键不存在,删除失败
def _resize(self, new_capacity):
old_table = self.table # 先保存旧表
self.capacity = new_capacity
self.table = [[] for _ in range(new_capacity)] # 建好扩容后的新表
for bucket in old_table: # 遍历旧表的每个桶
for k, v in bucket:
self.table[self._hash(k)].append((k, v)) # 重新哈希放入新表(表长变了,下标会变化)
# —— 手写哈希表的功能实测 ——
hm = MyHashMap() # 默认容量 8
for i in range(20):
hm.put(i, i * 10) # 插入 20 个键值对(超过 0.75 装载因子 → 触发扩容)
print('插入 20 个键值对后: size =', hm.size, ', capacity =', hm.capacity)
print('get(5) =', hm.get(5))
print('get(99) =', hm.get(99, '未找到'))
hm.put(5, 999) # 覆盖已有键
print('覆盖已有键 put(5, 999) 后 get(5) =', hm.get(5))
print('remove(5) =', hm.remove(5), ', 再 get(5) =', hm.get(5))
# 负数与字符串键
hm.put(-3, '负键') # 负数也能哈希
hm.put('python', '字符串键') # 字符串也能哈希(内置 hash 支持)
print('get(-3) =', hm.get(-3), ', get(\'python\') =', hm.get('python'))
插入 20 个键值对后: size = 20 , capacity = 32
get(5) = 50
get(99) = 未找到
覆盖已有键 put(5, 999) 后 get(5) = 999
remove(5) = True , 再 get(5) = None
get(-3) = 负键 , get('python') = 字符串键
§4 高频题精讲 A:两数之和 / 三数之和¶
题 1:两数之和(LeetCode 1,必背)¶
题目:给定数组与目标值 $target$,返回两数下标使 $a_i + a_j = target$。
核心公式:
$$a_j = target - a_i$$
思路:一次遍历,用哈希表记录「值 → 下标」。对每个 $a_i$,查 $target - a_i$ 是否已在表中——把 $O(n^2)$ 暴力降为 $O(n)$。
复杂度:时间 $O(n)$,空间 $O(n)$。
题 2:三数之和(LeetCode 15,去重是考点)¶
题目:找所有 $a_i + a_j + a_k = 0$ 的三元组,不能重复。
思路:排序 + 固定第一个数 + 双指针扫剩下区间。
为什么去重要先排序:排序后相同值相邻,跳过相同值即可避免重复三元组——用哈希去重还得额外 set 存结果。
复杂度:时间 $O(n^2)$,空间 $O(\log n)$(排序栈)。
💡 变形题:最接近的三数之和(16)、四数之和(18)——套路一样,排序 + 双指针。
✍️ §4.1 手算两数之和(哈希):[3,2,4] 找 6¶
哈希解法:每遍历一个元素,查
target - x是否已在表——3 个元素手算,看懂"一次遍历"的轨迹。
设定:nums=[3,2,4],target=6。哈希表初始为空。
第 1 步:x=3,查 6-3=3 不在表 → 入表 {3:0}
第 2 步:x=2,查 6-2=4 不在表 → 入表 {3:0, 2:1}
第 3 步:x=4,查 6-4=2 在表(下标 1) → 答案 [1, 2]
手算收获:
- 哈希把"找配对"从 $O(n^2)$ 暴力降到 $O(n)$:查表 $O(1)$ 均摊(冲突时退化为链表,本 notebook §3.1 哈希函数/冲突处理)
- 边遍历边查:不先建全表也能命中——因为答案要么在左边要么在右边,先入表的一定是"已经看过的左边"
- 返回的是下标不是值:所以存
{值: 下标};若题目要求返回元素本身,存集合即可 - 变体延伸:三数之和 = 排序 + 双指针(§4 题 2);四数之和同理——"降维"思路是高频考点
下面 numpy 复算。
# ---- §4.1 验证:numpy 复算两数之和 ----
nums = [3, 2, 4]
target = 6
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
print(f'答案 = [{seen[target - x]}, {i}]')
assert [seen[target - x], i] == [1, 2]
break
seen[x] = i
print('\n✓ 与手算一致')
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 1 两数之和:给定数组与目标值 target,返回两个下标使 a_i + a_j = target。
# 把暴力双重循环 O(n²) 降到一次遍历 O(n),是「空间换时间」的入门题。
# 【算法思路】一次遍历,用哈希表 seen 记录「值 → 下标」:对每个元素 x,
# 查另一半 b = target - x 是否已出现过;出现过即返回 [seen[b], i]。
# 【变量含义】nums=输入数组;target=目标和;seen=字典(键=元素值,值=首次出现下标);
# i=当前下标;x=当前值;b=所需的另一半(target - x)。
# 【循环不变量】遍历到位置 i 时,seen 中恰好记录了 nums[0..i-1] 所有元素的下标(每个值只存最早下标)。
# 【关键边界】必须「先查后存」:若先 seen[x]=i 再查,同一元素会被自己复用([3,3] 例会错);
# 返回值下标顺序是 [先出现者, 后出现者];无解返回空列表 [ ]。
# 【复杂度】时间 O(n)(每个元素 O(1) 查与存);空间 O(n)(哈希表最多装 n 个键)。
# ════════════════════════════════════════════════════════════════════════
# 1. 两数之和(LeetCode 1):一次遍历,用哈希表记录「值 → 下标」
# 核心公式:对每个 a_i,查 target - a_i 是否已在表中;把 O(n²) 暴力降为 O(n)
def two_sum(nums, target):
# 公式:b = target - a,边遍历边查哈希
seen = {} # 哈希表:值 → 下标
for i, x in enumerate(nums): # 遍历数组,i 为下标,x 为当前值
b = target - x # 需要的另一半 b
if b in seen: # 另一半已出现过 → 找到答案
return [seen[b], i] # 返回两个下标(先出现的在前)
seen[x] = i # 先查后存:避免同一个元素被复用两次
return [] # 无解返回空列表
print('test1:', two_sum([2, 7, 11, 15], 9)) # 期望 [0, 1]
print('test2:', two_sum([3, 3], 6)) # 期望 [0, 1]
print('test3:', two_sum([3, 2, 4], 6)) # 期望 [1, 2]
print('test4:', two_sum([1, 2, 3], 7)) # 期望 []
test1: [0, 1] test2: [0, 1] test3: [1, 2] test4: []
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 15 三数之和:找出所有 a_i + a_j + a_k = 0 的三元组,且结果不重复。
# 与两数之和不同,这里「去重」是真正的考点——必须靠排序 + 跳过相邻重复值实现。
# 【算法思路】① 先排序(相同值相邻,去重才可能 O(1) 完成);② 固定第一个数 nums[i];
# ③ 在剩余区间 [i+1, n-1] 用双指针 lo / hi 找两数之和 = -nums[i];
# ④ 找到一组后,lo 与 hi 都要跳过重复值,避免产生重复三元组。
# 【变量含义】nums=输入数组(被原地 sort 修改);res=结果列表;n=数组长度;
# i=固定首数的下标;lo / hi=双指针(左端 i+1、右端 n-1);s=当前三元组之和。
# 【循环不变量】对固定的 i:nums[lo] 与 nums[hi] 均已跳过与前一个位置相同的值 ⇒ 结果不重复;
# 外层 i 也跳过与 i-1 相同的值;[0, i) 中每个值只作为首数处理一次。
# 【关键边界】i 只循环到 n-3(后面至少留两个数);排序后 nums[i] > 0 直接 break(和不可能为 0);
# 双指针条件 lo < hi;找到解后 lo 右移且 hi 左移,并用两个 while 分别跳过重复;
# 空数组 / 长度小于 3 时循环天然不执行,返回 [ ]。
# 【复杂度】排序 O(n log n) + 固定 i 的 O(n²) 双指针扫描 ⇒ 总时间 O(n²);
# 空间 O(log n)(排序递归栈,不算结果数组)。
# ════════════════════════════════════════════════════════════════════════
# 2. 三数之和(LeetCode 15):排序 + 固定第一个数 + 双指针扫剩余区间,去重是真正考点
# 为什么先排序:排序后相同值相邻,跳过相邻重复值即可去重,避免用 set 额外存结果
def three_sum(nums):
nums.sort() # 先排序(O(n log n))
res = []
n = len(nums)
for i in range(n - 2): # 固定第一个数 nums[i],后面至少留两个数
if i > 0 and nums[i] == nums[i - 1]:
continue # 去重:同一数值只作第一个数一次
if nums[i] > 0:
break # 排序后首数>0,和不可能为 0
lo, hi = i + 1, n - 1 # 双指针:lo 指向 i 的下一个,hi 指向末尾
while lo < hi:
s = nums[i] + nums[lo] + nums[hi] # 当前三元组之和
if s < 0:
lo += 1 # 和太小 → 左指针右移,让和变大
elif s > 0:
hi -= 1 # 和太大 → 右指针左移,让和变小
else:
res.append([nums[i], nums[lo], nums[hi]]) # 和为 0 → 记录一组答案
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1 # 跳过重复的 lo
while lo < hi and nums[hi] == nums[hi + 1]:
hi -= 1 # 跳过重复的 hi
return res
print('test1:', three_sum([-1, 0, 1, 2, -1, -4])) # 期望 [[-1,-1,2],[-1,0,1]]
print('test2:', three_sum([0, 0, 0])) # 期望 [[0,0,0]]
print('test3:', three_sum([0, 1, 1])) # 期望 []
test1: [[-1, -1, 2], [-1, 0, 1]] test2: [[0, 0, 0]] test3: []
§5 高频题精讲 B:移动零 / 轮转数组 / 合并区间¶
题 3:移动零(LeetCode 283)¶
题目:原地把 0 移到末尾,保持非零元素相对顺序。
思路:快慢指针。slow 指向下一个非零元素应放的位置,fast 扫描:遇到非零就与 slow 交换。
复杂度:时间 $O(n)$,空间 $O(1)$。
题 4:轮转数组(LeetCode 189,三次反转法)¶
题目:数组右移 $k$ 位。
关键:先取 $k' = k \bmod n$($k$ 可能大于 $n$)。
三次反转公式:
$$\text{rotate}(k) = \text{rev}(0, n-1) \circ \text{rev}(0, k'-1) \circ \text{rev}(k', n-1)$$
为什么成立:整体反转让尾部元素到头部,再各自反转恢复两段内部顺序。
复杂度:时间 $O(n)$,空间 $O(1)$。
题 5:合并区间(LeetCode 56)¶
题目:合并所有重叠区间。
思路:按左端点排序;若当前区间左端点 $\le$ 结果末尾右端点则合并(右端点取 max),否则追加。
复杂度:时间 $O(n \log n)$(排序主导),空间 $O(n)$(结果)。
贪心正确性:排序后区间按左端点单调不减,新区间只可能与结果最后一个区间重叠——贪心成立。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】两道「原地操作」题:LeetCode 283 移动零(快慢指针)与 LeetCode 189 轮转数组(三次反转),
# 都要求不借助额外数组、原地完成,是数组底层布局理解的高频面试题。
# 【算法思路】移动零:快慢指针。slow 指向下一个非零元素应放的位置,fast 逐个扫描,
# 遇到非零就与 slow 交换并 slow+1 ⇒ 非零全部前移、0 自然落到后面且相对顺序保持。
# 轮转数组:先 k %= n 消除多余轮转,再用三次反转 rev(0,n-1) → rev(0,k-1) → rev(k,n-1):
# 整体反转让尾部元素跑到头部,再各自反转恢复两段内部顺序。
# 【变量含义】nums=输入数组(原地修改并返回);slow=下一个非零元素的落点下标;
# fast=扫描指针;n=数组长度;k=右移位数(先取模 n);
# rev(i, j)=辅助函数,把 nums[i..j] 用双指针两端交换反转。
# 【循环不变量】移动零:循环到 fast 时,[0, slow) 已全部是非零且保持原相对顺序;
# 轮转数组:三次反转是恒等变换的拆解——每次 rev 后都恰好朝目标前进一步。
# 【关键边界】k 可能大于 n,必须 k %= n(否则第二次反转 rev(0,k-1) 越界或结果错误);
# 移动零交换时 fast 可能等于 slow(原地自交换,无害);空数组 / n=0 时 k%n 除零需注意。
# 【复杂度】移动零:时间 O(n)、空间 O(1);轮转数组:三次反转各 O(n)、空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 3. 移动零(LeetCode 283):快慢指针原地重排,非零元素保持相对顺序
def move_zeroes(nums):
slow = 0 # slow 指向下一个非零元素应放的位置
for fast in range(len(nums)): # fast 扫描整个数组
if nums[fast] != 0: # 遇到非零元素
nums[slow], nums[fast] = nums[fast], nums[slow] # 与 slow 处交换 → 非零前移、0 后移
slow += 1 # slow 前进,准备接收下一个非零
return nums
# 4. 轮转数组(LeetCode 189):三次反转法,原地 O(1) 空间
def rotate(nums, k):
n = len(nums)
k %= n # 关键:k 可能大于 n
def rev(i, j): # 辅助函数:反转 nums[i..j]
while i < j: # 双指针从两端向中间交换
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
rev(0, n - 1) # 第 1 次:整体反转 → 尾部元素跑到头部
rev(0, k - 1) # 第 2 次:反转前 k 个,恢复这段的内部顺序
rev(k, n - 1) # 第 3 次:反转剩余段,恢复这段的内部顺序
return nums
print('move_zeroes:', move_zeroes([0, 1, 0, 3, 12])) # 期望 [1,3,12,0,0]
print('rotate1:', rotate([1, 2, 3, 4, 5, 6, 7], 3)) # 期望 [5,6,7,1,2,3,4]
print('rotate2:', rotate([-1, -100, 3, 99], 2)) # 期望 [3,99,-1,-100]
print('rotate3(k>n):', rotate([1, 2, 3], 5)) # 期望 [2,3,1]
move_zeroes: [1, 3, 12, 0, 0] rotate1: [5, 6, 7, 1, 2, 3, 4] rotate2: [3, 99, -1, -100] rotate3(k>n): [2, 3, 1]
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 56 合并区间:给定若干区间,合并所有重叠部分,返回不重叠的区间列表。
# 核心套路是「排序 + 贪心」,背后依赖区间按左端点排序后的单调性。
# 【算法思路】按左端点升序排序后,区间从左到右逐个处理:
# 若当前区间左端点 ≤ 结果列表末尾区间的右端点 ⇒ 重叠,合并(右端点取两者 max);
# 否则不重叠,直接作为新区间追加。贪心正确性:排序后新遇到的区间只可能与
# 结果列表的最后一个区间重叠(所有更早区间都已处理完毕且更靠左)。
# 【变量含义】intervals=输入区间列表(原地 sort);res=合并结果列表;
# lo / hi=当前区间的左 / 右端点;res[-1][1]=结果末区间的右端点。
# 【循环不变量】每轮循环开始时,res 中的区间互不重叠、按左端点递增、且已覆盖处理过的所有输入。
# 【关键边界】重叠判断用 lo <= res[-1][1](端点相接 [1,4] 与 [4,5] 也算重叠,应合并为 [1,5]);
# 合并时右端点取 max(新区间可能完全在内部,如 [1,4] 后接 [0,4] 这类乱序输入要先排序);
# 空输入 / 单区间直接原样返回。
# 【复杂度】时间 O(n log n)(排序主导),空间 O(n)(结果列表,不计输入)。
# ════════════════════════════════════════════════════════════════════════
# 5. 合并区间(LeetCode 56):按左端点排序后贪心合并,新区间只可能与结果最后一个区间重叠
def merge(intervals):
intervals.sort(key=lambda x: x[0]) # 按区间左端点升序排序
res = [] # 存放合并后的区间
for lo, hi in intervals: # 逐个处理区间
if res and lo <= res[-1][1]: # 与结果末区间重叠(当前左端点 ≤ 末右端点)
res[-1][1] = max(res[-1][1], hi) # 合并:更新右端点
else:
res.append([lo, hi]) # 不重叠 → 直接作为新区间加入
return res
print('test1:', merge([[1, 3], [2, 6], [8, 10], [15, 18]])) # 期望 [[1,6],[8,10],[15,18]]
print('test2:', merge([[1, 4], [4, 5]])) # 期望 [[1,5]]
print('test3:', merge([[1, 4], [0, 4]])) # 期望 [[0,4]]
print('test4:', merge([])) # 期望 []
test1: [[1, 6], [8, 10], [15, 18]] test2: [[1, 5]] test3: [[0, 4]] test4: []
§6 高频题精讲 C:哈希五题(每题都是一类套路)¶
题 6:最长连续序列(LeetCode 128)¶
题目:无序数组里最长的连续数字序列长度(如 [100,4,200,1,3,2] → 4)。
套路:全部放进 set,只从连续段的起点开始数——若 $x-1$ 已在集合则跳过 $x$。
为什么总复杂度是 $O(n)$:每个元素最多被访问两次(一次被跳过、一次作为某段内部被数过),不是 $O(n^2)$。
题 7:除自身以外数组的乘积(LeetCode 238,禁止除法)¶
题目:返回 $b_i = \prod_{j \neq i} a_j$。
公式(左前缀 × 右后缀):
$$b_i = \underbrace{(a_0 a_1 \cdots a_{i-1})}_{\text{left}[i]} \times \underbrace{(a_{i+1} \cdots a_{n-1})}_{\text{right}[i]}$$
思路:先从左往右算左前缀积(复用输出数组),再从右往左乘右后缀积——空间 $O(1)$(不计输出)。
题 8:和为 K 的子数组(LeetCode 560,前缀和套路)¶
题目:连续子数组和为 $k$ 的个数。
公式:子数组和 = 前缀和之差
$$\sum_{t=i}^{j} a_t = P_j - P_{i-1} \quad \Rightarrow \quad P_j - k = P_{i-1}$$
思路:遍历时维护前缀和 $P_j$,用哈希表统计「每个前缀和出现次数」,累加 $P_j - k$ 的次数。
注意:存在负数和 0 元素时不能用滑动窗口(单调性失效)——必须前缀和。
补充:差分数组(区间加减,前缀和的逆运算):对区间 $[l, r]$ 统一加 $v$,只需 $diff[l] += v, \; diff[r+1] -= v$,最后对 $diff$ 求前缀和还原原数组——多次区间操作从 $O(nk)$ 降到 $O(n+k)$(典型题:LeetCode 370 区间加法)。
题 9:多数元素(LeetCode 169,Boyer-Moore 投票)¶
题目:出现次数 $> \lfloor n/2 \rfloor$ 的元素。
思路:候选者 + 票数。票数归零换候选者,不同元素互相抵消。
证明:众数数量超过其他所有元素之和,两两抵消后众数必然留下。
复杂度:时间 $O(n)$,空间 $O(1)$。
题 10:缺失的第一个正数(LeetCode 41,原地哈希套路)¶
题目:未排序整数数组中,返回缺失的最小正整数(如 [3,4,-1,1] → 2)。
套路——用数组下标当哈希桶:值 $v$ 若在 $[1, n]$,它的「正确归宿」是下标 $v-1$。遍历时把每个 $v$ 交换到 $nums[v-1]$;若 $v \le 0$ 或 $v > n$ 或已就位,直接跳过。一遍交换后扫一遍,找第一个 $nums[i] \ne i+1$ 的位置返回 $i+1$;全部就位则返回 $n+1$。
关键点:空间 $O(1)$ 复用输入数组——不另开哈希表,把原数组就地改造成「下标 → 值」的桶,用数组本身完成哈希表的存与查,省掉 $O(n)$ 额外空间。
复杂度:时间 $O(n)$(每个元素最多被交换一次到正确位置),空间 $O(1)$(不计输入)。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 128 最长连续序列:无序数组里最长连续数字段(相邻差 1)的长度。
# 经典哈希套路:全部进 set,且「只从连续段的起点开始向后数」,保证总复杂度是 O(n)。
# 【算法思路】把数组放进 set(O(1) 存在性判断);遍历每个元素 x:
# 若 x-1 也在 set 中,说明 x 不是连续段的起点,直接跳过(避免重复统计同一段);
# 若 x 是起点,就 while 向后延伸 x+1, x+2, … 统计段长,并更新 best。
# 【变量含义】nums=输入数组;s=元素集合;best=目前最长连续段长度;
# x=当前考察元素;length=以 x 为起点的连续段长度(初始 1)。
# 【循环不变量】每个连续段只会被统计一次——只有段的最小元素会进入 while 延伸,
# 其余元素因 x-1 在集合中而跳过 ⇒ 每个元素最多被访问两次(跳过 + 作为段内元素)。
# 【关键边界】判断起点用 x-1 in s(而非 x+1);延伸用 while x + length in s;
# 空数组返回 0;重复元素在 set 中自动去重([1,2,0,1] 用例长度 3 依赖这一点)。
# 【复杂度】时间 O(n):集合构建 O(n),每个元素至多被起点延伸访问一次(不是 O(n²));
# 空间 O(n)(存集合)。
# ════════════════════════════════════════════════════════════════════════
# 6. 最长连续序列(LeetCode 128):全部进 set,只从连续段的起点开始数 → 总复杂度 O(n)
def longest_consecutive(nums):
s = set(nums) # set 支持 O(1) 的存在性判断
best = 0 # 记录目前找到的最长连续长度
for x in s: # 遍历每个元素
if x - 1 in s: # 存在前驱 x-1 → x 不是连续段的起点
continue # 不是起点,跳过
length = 1 # 从起点开始向后数
while x + length in s: # 向后延伸:x+1, x+2, ... 逐个检查
length += 1
best = max(best, length) # 更新最长长度
return best
print('test1:', longest_consecutive([100, 4, 200, 1, 3, 2])) # 期望 4
print('test2:', longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1])) # 期望 9
print('test3:', longest_consecutive([1, 2, 0, 1])) # 期望 3
print('test4:', longest_consecutive([])) # 期望 0
test1: 4 test2: 9 test3: 3 test4: 0
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 238 除自身以外数组的乘积:返回 b_i = 除 a_i 外所有元素之积,
# 且题目禁止使用除法——标准解法是「左前缀积 × 右后缀积」,额外空间 O(1)。
# 【算法思路】先从左往右一遍:res[i] = a[0]*a[1]*…*a[i-1](左前缀积,res[0] 置 1);
# 再从右往左一遍:用变量 right 累计右后缀积(right = a[i+1]*…*a[n-1]),
# 把 res[i] *= right,两遍相乘即得到除自身外所有元素的乘积。
# 【变量含义】nums=输入数组;n=数组长度;res=输出数组(第一遍装左前缀积,第二遍变成最终答案);
# right=右后缀积(从右向左累计);i=遍历下标。
# 【循环不变量】第一遍结束后:res[i] = ∏_{t<i} nums[t](左前缀积);
# 第二遍扫描到 i 时:right = ∏_{t>i} nums[t](右后缀积),res[i] 即将变为最终答案。
# 【关键边界】res[0] 必须初始化为 1(空前缀积);第二遍从 n-1 倒序到 0;
# 含 0 的元素照常工作(0 只影响含它的位置),无需特判——两遍乘法天然正确处理。
# 【复杂度】时间 O(n)(恰好两遍线性扫描);空间 O(1)(不计输出数组 res,right 是常数变量)。
# ════════════════════════════════════════════════════════════════════════
# 7. 除自身以外数组的乘积(LeetCode 238):左前缀积 × 右后缀积,禁止用除法
def product_except_self(nums):
n = len(nums)
res = [1] * n # 复用输出数组,先装左前缀积
# 第一遍:res[i] = 左前缀积 a0*a1*...*a(i-1)
for i in range(1, n):
res[i] = res[i - 1] * nums[i - 1] # 递推:左前缀积 = 上一个左前缀积 × 前一个元素
# 第二遍:从右往左乘右后缀积
right = 1 # right 维护右后缀积(从右往左累计)
for i in range(n - 1, -1, -1): # 从右往左遍历
res[i] *= right # 左前缀积 × 右后缀积 = 除自身外的乘积
right *= nums[i] # 更新右后缀积,供下一个位置使用
return res
print('test1:', product_except_self([1, 2, 3, 4])) # 期望 [24, 12, 8, 6]
print('test2:', product_except_self([-1, 1, 0, -3, 3])) # 期望 [0, 0, 9, 0, 0]
print('test3:', product_except_self([0, 0])) # 期望 [0, 0]
test1: [24, 12, 8, 6] test2: [0, 0, 9, 0, 0] test3: [0, 0]
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 560 和为 K 的子数组:统计连续子数组(元素和恰好为 k)的个数。
# 核心套路是「前缀和 + 哈希计数」,能把暴力 O(n²) 降为 O(n)。
# 【算法思路】子数组和可写成前缀和之差:sum[i..j] = P_j - P_{i-1} = k ⇔ P_{i-1} = P_j - k。
# 因此只需一次遍历:维护当前前缀和 prefix,统计「prefix - k」这个值在之前出现过几次,
# 累加进答案;再把当前 prefix 的计数 +1 存入哈希表 seen。
# 【变量含义】nums=输入数组;k=目标和;count=满足条件的子数组个数;
# prefix=当前前缀和 P_j;seen=字典(键=前缀和,值=出现次数)。
# 【循环不变量】遍历到元素 x 时,seen 已记录 nums[0..j-1] 所有前缀和的出现次数;
# count 恰好等于「以当前位置结尾的、和为 k 的连续子数组」个数(由 P_j - k 命中次数决定)。
# 【关键边界】seen 必须预置 {0: 1}(空前缀 P_{-1}=0 出现 1 次),否则漏掉「从数组头开始的子数组」;
# 先累加 count 再登记当前 prefix(避免把当前前缀本身算进去);
# 存在负数 / 0 时滑动窗口的单调性失效,必须用前缀和(本单元用例 test4 即负数场景)。
# 【复杂度】时间 O(n)(一次遍历,哈希操作均摊 O(1));空间 O(n)(哈希表存前缀和)。
# ════════════════════════════════════════════════════════════════════════
# 8. 和为 K 的子数组(LeetCode 560):前缀和 + 哈希表统计出现次数
# 核心等式:子数组和 = P_j - P_{i-1} = k,即 P_{i-1} = P_j - k,统计 P_j - k 出现过的次数即可
def subarray_sum(nums, k):
# 前缀和:P_j - P_{i-1} = k ⇔ 统计 P_j - k 在之前出现几次
count = 0 # 满足条件的子数组个数
prefix = 0 # 当前前缀和 P_j
seen = {0: 1} # 前缀和为 0 出现 1 次(空前缀)
for x in nums:
prefix += x # 累加前缀和
count += seen.get(prefix - k, 0) # 之前 prefix-k 出现的次数 = 以当前位置结尾的合法子数组数
seen[prefix] = seen.get(prefix, 0) + 1 # 把当前前缀和计数 +1,供后续使用
return count
print('test1:', subarray_sum([1, 1, 1], 2)) # 期望 2
print('test2:', subarray_sum([1, 2, 3], 3)) # 期望 2
print('test3:', subarray_sum([0, 0, 0], 0)) # 期望 6
print('test4:', subarray_sum([-1, -1, 1], 0)) # 期望 1([-1,1])
test1: 2 test2: 2 test3: 6 test4: 1
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 169 多数元素:找出出现次数严格大于 n/2 的元素,要求时间 O(n)、空间 O(1)。
# 标准解法是 Boyer-Moore 投票法——不排序、不开哈希表。
# 【算法思路】维护一个候选者 candidate 和净票数 votes:
# 遇到与 candidate 相同的元素票数 +1,不同元素票数 -1(互相抵消);
# 票数归零时更换候选者为当前元素。因为众数出现次数超过其他所有元素之和,
# 两两抵消后众数必然留下成为最后的候选者。
# 【变量含义】nums=输入数组;candidate=当前候选者(初始 None);
# votes=候选者的净票数(初始 0);x=当前扫描元素。
# 【循环不变量】扫描到任意位置时,若把已处理区间按「候选者 vs 非候选者」分组,
# 则 votes 等于两组人数之差;区间内的抵消不影响众数在全局的主导地位。
# 【关键边界】votes == 0 时更换候选者(且把当前元素作为新候选者);
# 题目保证众数存在(出现次数 > n/2),否则需二次扫描验证候选者是否真过半;
# 单元素数组直接返回该元素。
# 【复杂度】时间 O(n)(一次扫描);空间 O(1)(只存候选者与票数两个变量)。
# ════════════════════════════════════════════════════════════════════════
# 9. 多数元素(LeetCode 169):Boyer-Moore 投票法,时间 O(n)、空间 O(1)
def majority_element(nums):
# Boyer-Moore 投票:不同元素互相抵消,最后剩下的候选者即众数
candidate = None # 当前候选者
votes = 0 # 候选者的净票数
for x in nums:
if votes == 0: # 票数归零 → 更换候选者
candidate = x
votes += 1 if x == candidate else -1 # 相同元素 +1 票,不同元素 -1 票(互相抵消)
return candidate # 众数数量过半,抵消后必然剩下
print('test1:', majority_element([3, 2, 3])) # 期望 3
print('test2:', majority_element([2, 2, 1, 1, 1, 2, 2])) # 期望 2
print('test3:', majority_element([1])) # 期望 1
# 合法性校验:多数元素出现次数必须 > n//2
def check(nums):
m = majority_element(nums)
return nums.count(m) > len(nums) // 2
print('合法性校验:', check([2, 2, 1, 1, 1, 2, 2]), check([3, 2, 3]))
test1: 3 test2: 2 test3: 1 合法性校验: True True
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 41 缺失的第一个正数:未排序数组中缺失的最小正整数,要求空间 O(1)。
# 标准套路是「原地哈希」——复用输入数组当下标哈希桶,不另开哈希表。
# 【算法思路】值 v ∈ [1, n](n 为数组长度)的元素,它的「正确归宿」是下标 v-1;
# 遍历时把每个合法值交换到 nums[v-1];越界(v < 1 或 v > n)或已就位则跳过;
# 一遍交换结束后,再扫描找第一个 nums[i] != i+1 的位置,返回 i+1;
# 若 1..n 全部就位,说明答案在数组之外,返回 n+1。
# 【变量含义】nums=输入数组(被原地改造为「下标 → 值」的桶);n=数组长度;
# i=扫描指针;v=nums[i] 的稳定副本(交换前先存下,避免下标随值联动错位)。
# 【循环不变量】对已处理过的位置 i:要么 nums[i] 已就位(nums[i] == i+1),
# 要么 nums[i] 越界(无需归位);循环继续处理那些刚被交换回来、尚未归位的值。
# 【关键边界】交换前必须先存 v = nums[i]:直接写元组赋值 nums[i], nums[nums[i]-1] = … 会因
# 左边从右到左求值顺序导致下标错位(代码 docstring 中已详述该踩坑);
# 交换成功后 i 不前进(换回来的值下一轮继续检查);空数组返回 1;全就位返回 n+1。
# 【复杂度】时间 O(n):每个值最多被交换一次到正确位置,整体线性;
# 空间 O(1):完全复用输入数组,不申请额外结构。
# ════════════════════════════════════════════════════════════════════════
# 10. 缺失的第一个正数(LeetCode 41):原地哈希——用数组下标当哈希桶,空间 O(1) 复用输入数组
def first_missing_positive(nums):
"""原地哈希:用数组下标当哈希桶,空间 O(1) 复用输入数组。
nums[i] 的正确归宿是 nums[nums[i]-1];值不在 [1, n] 的直接忽略。
踩坑提醒:不要直接写 nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
——元组赋值右边先求值、左边从左到右赋值,nums[i] 一变,
nums[nums[i]-1] 里的下标就跟着错位,交换结果就错了。
先存 v = nums[i],让交换左右都引用稳定的 v;换回来的值下一轮再检查(i 不前进)。
"""
n = len(nums) # 数组长度
i = 0 # 扫描指针
while i < n: # 遍历:把每个值放到它「该在」的位置
v = nums[i] # 先取出当前值存到稳定变量 v
if 1 <= v <= n and nums[v - 1] != v: # v 在 [1,n] 且还没就位 → 需要交换
nums[i], nums[v - 1] = nums[v - 1], v # v 已存好,下标与值都稳定
# 换回来的值可能也要归位:i 不前进,下一轮继续处理当前位置
else:
i += 1 # v 越界或已就位 → 跳过,处理下一个位置
for i in range(n): # 扫描:找第一个 nums[i] != i+1 的位置
if nums[i] != i + 1:
return i + 1 # 该位置缺失的数就是答案
return n + 1 # 1..n 全部就位 → 答案是 n+1
# 用断言验证正确性:覆盖常规、单元素、空数组等场景
# 题目要求的最小正整数
assert first_missing_positive([1, 2, 0]) == 3
assert first_missing_positive([3, 4, -1, 1]) == 2
assert first_missing_positive([7, 8, 9, 11, 12]) == 1
assert first_missing_positive([1]) == 2
assert first_missing_positive([2]) == 1
assert first_missing_positive([]) == 1
# 边界:全非正、大数、重复、已就位
assert first_missing_positive([-1, -5, 0]) == 1
assert first_missing_positive([10 ** 9]) == 1
assert first_missing_positive([1, 1]) == 2
assert first_missing_positive([2, 1]) == 3
print('缺失的第一个正数:全部断言通过')
缺失的第一个正数:全部断言通过
§7 复杂度总表(背熟)¶
数组 / list¶
| 操作 | 复杂度 | 说明 |
|---|---|---|
| 随机访问 a[i] | $O(1)$ | 基址 + 偏移 |
| 尾部 append / pop | $O(1)$ 均摊 | 翻倍扩容均摊 |
| 头部 / 中间插入删除 | $O(n)$ | 元素搬移 |
| 按值查找(无序) | $O(n)$ | 线性扫描 |
| 切片 a[i:j] | $O(k)$ | 新列表拷贝 |
| sort() | $O(n \log n)$ | Timsort,稳定 |
哈希表(dict / set)¶
| 操作 | 复杂度 | 说明 |
|---|---|---|
| 插入 / 删除 / 查找 | $O(1)$ 均摊 | 冲突退化 $O(n)$ |
| 遍历 | $O(n)$ | Python 3.7+ 保持插入顺序 |
| 扩容 resize | 单次 $O(n)$,均摊 $O(1)$ | 翻倍 + rehash |
均摊分析(为什么翻倍扩容均摊 $O(1)$)¶
插入 $n$ 个元素,扩容总搬移成本:
$$n + \frac{n}{2} + \frac{n}{4} + \cdots < 2n = O(n)$$
$$\text{均摊每次插入} = \frac{O(n)}{n} = O(1)$$
💡 hash 冲突退化:若哈希函数固定且攻击者构造同余键,单桶链长可达 $O(n)$——Python 3.3+ 用随机盐(PYTHONHASHSEED)防哈希碰撞攻击。
§8 常见 bug 与边界(面试踩坑区)¶
- 空数组 / 单元素:
nums[0]越界——先判len(nums) - 负下标陷阱:
nums[-1]是最后一个元素,不是「倒数第二个」 - k 大于 n:轮转、二分等一律先
k %= n - 哈希键必须不可变:
dict[list]直接 TypeError;tuple 可作键 - 重复元素:两数之和返回下标,同一元素不能复用两次——先查哈希再写入,保证不误用自己
- 整数溢出:Python 无溢出;C++/Java 里
a + b可能溢出(用 C++ 面试时注意) - 前缀和别忘
{0: 1}:和为 K 的子数组最容易漏掉「从头开始的子数组」 - 三数之和去重顺序:排序后跳过相邻重复值,而不是最后 set 去重
- 原地操作 vs 返回值:看清题目要求(移动零是否返回)
- list 的 in 是 $O(n)$:set / dict 的 in 才是 $O(1)$——别混用
⚠️ 最隐蔽的一个:
for i in range(len(nums))里同时nums.pop(i)会导致索引错位——要删元素时倒序遍历或先收集下标。
§9 面试追问与扩展(加分项)¶
9.1 大数据场景:内存装不下怎么办¶
- 去重:布隆过滤器(Bloom Filter)——位数组 + $k$ 个哈希函数,允许假阳性、无假阴性
- 频次统计:Count-Min Sketch 近似计数
- 精确去重:外部排序 + 归并
9.2 Python dict 实现细节(高频八股)¶
- Python 3.6+ 保持插入顺序(3.7 起为语言规范);3.11 起紧凑 dict 节省内存
- 冲突处理:开放寻址 + 伪随机探测(随机盐防哈希碰撞攻击)
- dict vs set:底层都是哈希表;dict 存「键→值」,set 存「键集合」
- 面试手写时用普通 dict +
get即可,能讲清原理更加分
9.3 手撕题预告(后续主题覆盖)¶
- LRU 缓存(哈希 + 双向链表)→ 链表主题
- 前缀树 Trie(哈希的树形推广)→ 树主题
- 字符串哈希 / 滚动哈希 → 字符串主题
§10 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
每题先自己写,再看答案思路。会写 = 能讲清复杂度 + 边界。
L1 必会(10 题)¶
- 1. 两数之和(LeetCode 1)
- 2. 移动零(283)
- 3. 合并两个有序数组(88)
- 4. 多数元素(169)
- 5. 只出现一次的数字(136)
- 6. 有效的字母异位词(242)
- 7. 轮转数组(189)
- 8. 找出数组交集(349)
- 9. 存在重复元素(217)
- 10. 买卖股票的最佳时机(121,贪心/DP)
L2 进阶(10 题)¶
- 11. 三数之和(15)
- 12. 最长连续序列(128)
- 13. 除自身以外数组的乘积(238)
- 14. 和为 K 的子数组(560)
- 15. 合并区间(56)
- 16. 字母异位词分组(49)
- 17. 颜色分类(75)
- 18. 最大子数组和(53)
- 19. 螺旋矩阵(54)
- 20. 下一个排列(31)
L3 挑战(5 题)¶
- 21. 缺失的第一个正数(41)
- 22. 最大矩形(85)
- 23. 和为 K 的最长子数组(面试手撕)
- 24. 快照数组(1146)
- 25. 网格照明(1001)
自测要点¶
- 每题能写出最优复杂度解法 + 一个反例验证
- 讲清「为什么哈希能把 $O(n^2)$ 变 $O(n)$」——用「空间换时间」一句话概括
- 手写链地址哈希表 5 分钟内完成(含扩容)