🎯 01-数据结构与算法 · 主题 2:双指针与滑动窗口¶
数组题两大高频套路。双指针把 $O(n^2)$ 暴力降为 $O(n)$,滑动窗口把「连续子区间」问题统一为 $O(n)$。 本 notebook 目标:掌握三种指针形态 → 背熟窗口四要素 → 吃透 7 道高频题 → 通过 25 道自测。
前置:主题 1(数组/哈希)。运行环境:Python 3.8+,无第三方依赖。
核心概念¶
(a) 🗂️ 双指针与滑动窗口:三种形态 + 窗口四要素¶
双指针把 O(n²) 暴力降为 O(n),滑动窗口把"连续子区间"问题统一成 O(n)。本 notebook 掌握三种指针形态与窗口四要素,精讲 9 道高频题。
flowchart TB
N1["🎯 套路总览:三种形态"] --> N2["相向双指针:167 / 11 盛水"]
N2 --> N3["接雨水 42:双指针推导"]
N1 --> N4["同向快慢指针:26 原地去重"]
N1 --> N5["滑动窗口万能模板(四要素)"]
N5 --> N6["最长类窗口:无重复子串 3"]
N5 --> N7["最短类窗口:最小覆盖 76"]
N5 --> N8["进阶:子序列 392 / 回文 5"]
N6 --> N9["复杂度总表与自测"]
N7 --> N9
N8 --> N9
- N1 · 套路总览:双指针不是一种数据结构,而是一套"用两根指针减少重复扫描"的套路;滑动窗口是它的特例,专治"连续子数组/子串"问题。
- N2 · 相向双指针:左指针向右、右指针向左,典型题是两数之和 II 和盛最多水的容器。核心是"按单调性排除不可能的解",从而不漏解地扫一遍。
- N3 · 接雨水 42:双指针的巅峰推导:左右指针记录两侧最高柱,哪边矮就结算哪边,一次扫描 O(n) 出答案,是"左右夹逼"的经典。
- N4 · 同向快慢指针:慢指针写结果位置、快指针找新元素,原地去重(LeetCode 26)就是这么一题,也是数组原地重排的通用手法。
- N5 · 滑动窗口万能模板:四要素——右指针扩张、收缩条件、窗口内容维护、答案更新时机。把这四步背熟,所有窗口题都是同一个套路。
- N6 · 最长类窗口:无重复字符的最长子串是"最长类"窗口:窗口内用哈希记录字符,遇到重复就收缩左边界,求的是"能撑到多长"。
- N7 · 最短类窗口:最小覆盖子串是"最短类"窗口:先扩张到满足条件,再收缩找最短,"欠账表 + 计数"是标准模板。
- N8 · 进阶:用双指针判断子序列(392)、用中心扩展求最长回文子串(5),属于提升篇的加分武器。
- N9 · 复杂度总表与自测:结尾的复杂度总表说明三种形态、最短类 vs 最长类窗口在不同题型下的选择,配 L1/L2/L3 自测清单收尾。
§1 套路总览:三种形态 + 心智模型¶
三种形态¶
| 形态 | 指针移动 | 典型题 |
|---|---|---|
| 相向双指针 | 左指针向右、右指针向左 | 两数之和 II、盛水容器、接雨水、三数之和 |
| 同向快慢指针 | 快指针扫描、慢指针记录位置 | 移动零、去重、链表中点 |
| 滑动窗口 | 右指针扩展、左指针收缩,维护区间 | 无重复最长子串、最小覆盖子串 |
心智模型¶
- 相向:两端夹逼,利用单调性缩小搜索空间——每次移动必然排除掉一部分不可能的解
- 同向:快指针负责遍历,慢指针标记「下一个写入位置」,一趟原地完成
- 滑动窗口:窗口 $[l, r)$ 是数组上一个连续区间;右扩找可行、左缩找最优,每个元素最多进出窗口各一次
什么时候用滑动窗口(判断口诀)¶
- ✅ 要求连续子数组/子串 + 有窗口条件的约束(和、无重复、覆盖)
- ✅ 数组全为正数时「和」类问题;字符类问题天然适合
- ❌ 有负数时「和 == k」类问题不能用滑动窗口(窗口和单调性失效)→ 用前缀和(主题 1 的 560 题)
§2 相向双指针:两数之和 II / 盛水容器¶
题 1:两数之和 II - 输入有序数组(LeetCode 167)¶
题目:有序数组,找两数之和等于 $target$。
公式:
$$a_{lo} + a_{hi} = target$$
单调性推理(为什么指针移动正确):
若 $a_{lo} + a_{hi} < target$,说明和太小——因为 $a_{hi}$ 已是最大,只能增大 $a_{lo}$($lo \leftarrow lo+1$); 若和 $> target$,同理只能减小 $a_{hi}$($hi \leftarrow hi-1$)。每次移动排除一行/一列候选,共 $O(n)$ 步。
题 2:盛最多水的容器(LeetCode 11)¶
题目:两条垂线之间能装多少水。
公式:
$$S(l, r) = \min(h_l, h_r) \times (r - l)$$
关键推理:固定 $l$ 时,$r$ 越远越好,但容量受短板 $\min(h_l, h_r)$ 限制。若 $h_l < h_r$,任何其他右端点 $r'$ 与 $l$ 组成的容器,高度 $\le h_l$ 且宽度更小,必然更差——所以移动短板一侧,不会漏掉最优解。
复杂度:两者都是时间 $O(n)$,空间 $O(1)$。
✍️ §2.1 手算双指针两大招:相向求和 + 滑动窗口去重¶
相向双指针:和太大右指针左移,太小左指针右移;滑动窗口:右扩 + 遇重收缩——两道题手算。
第 1 招:两数之和 II(有序 [2,7,11,15],target=9)
| 步 | l | r | 和 | 动作 |
|---|---|---|---|---|
| 1 | 0 | 3 | $2+15=17>9$ | r=2 |
| 2 | 0 | 2 | $2+11=13>9$ | r=1 |
| 3 | 0 | 1 | $2+7=9$ | ✓ 返回 [0,1] |
第 2 招:无重复字符最长子串("abcabcbb")
窗口右扩:[a]→[ab]→[abc](长 3),遇第二个 a 收缩左端,窗口 [b,c,a] 仍长 3……最终最长 $=3$("abc")。
手算收获:
- 相向双指针为何不漏解:有序数组里 $l$ 固定时 $r$ 右移和更大、$r$ 固定时 $l$ 左移和更小——每步排除一整块不可能区间(本 notebook §12.1 追问)
- 滑动窗口四要素:右扩、收缩条件、更新答案、窗口字典——"无重复"用集合/哈希维护,遇重复就跳
seen[ch]+1(§5 万能模板) - 复杂度都是 $O(n)$:指针/窗口左右各扫一遍,绝不回溯——比暴力 $O(n^2)$ 快一个量级
- 面试速答:单调性(有序/可行区间连续)是窗口成立的证明,不是死记模板
下面 numpy 复算。
# ---- §2.1 验证:numpy 复算双指针与滑动窗口 ----
nums = [2, 7, 11, 15]
target = 9
l, r = 0, len(nums) - 1
while l < r:
s = nums[l] + nums[r]
if s == target:
print(f'两数之和 → [{l},{r}](3 步)')
break
elif s < target:
l += 1
else:
r -= 1
assert (l, r) == (0, 1)
s = 'abcabcbb'
max_len = l2 = 0
seen = {}
for r2, ch in enumerate(s):
if ch in seen and seen[ch] >= l2:
l2 = seen[ch] + 1
seen[ch] = r2
max_len = max(max_len, r2 - l2 + 1)
print(f'"abcabcbb" 最长无重复 = {max_len}')
assert max_len == 3
print('\n✓ 与手算一致')
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】两道「相向双指针」经典题:LeetCode 167 两数之和 II(输入有序)与 LeetCode 11 盛最多水的容器。
# 共同点:指针从两端向中间夹逼,利用问题内在的单调性,把 O(n²) 暴力降到 O(n)。
# 【算法思路】167:有序数组两指针头尾相向,当前和 s = numbers[lo]+numbers[hi]:
# s < target 时只能右移 lo(右端已是最大值,左移只会更小);s > target 时只能左移 hi。
# 11:面积 S = min(h[lo], h[hi]) × (hi-lo),容量受短板限制;永远移动「更矮」的一侧——
# 因为若 h[lo] < h[hi],固定 lo 时任何其他右端点都更矮更窄,最优解不会因移动 lo 而丢失。
# 【变量含义】numbers / height=输入数组;target=目标和;lo、hi=左右指针;s=当前两数之和;
# h=当前容器高度(短板高度);best=记录的最大面积。
# 【循环不变量】167:每轮循环中,答案若存在必在 [lo, hi] 内(被排除的端对都不可能等于 target);
# 11:best 恒为「已扫描过的所有区间」中的最大面积;指针向中间收缩时不会漏掉更优解。
# 【关键边界】循环条件都是 lo < hi(不能相等,否则同一元素被用两次 / 宽度为 0);
# 167 的下标从 1 开始(返回 lo+1, hi+1);11 中高度相等时移动哪侧都行(代码移动右指针);
# 167 无解返回空列表 [ ]。
# 【复杂度】两题均为时间 O(n)(指针各自单调移动,总步数 ≤ n);空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 1. 两数之和 II(LeetCode 167,输入有序):相向双指针,利用「和」的单调性省掉一重循环
# 推理:和太小只能增大左指针(右已是最大);和太大只能减小右指针——每次移动排除一排候选,O(n)
def two_sum_ii(numbers, target):
# 有序数组:相向双指针,利用和的单调性
lo, hi = 0, len(numbers) - 1 # 左指针在头、右指针在尾
while lo < hi:
s = numbers[lo] + numbers[hi] # 当前两数之和
if s == target:
return [lo + 1, hi + 1] # 本题下标从 1 开始
elif s < target:
lo += 1 # 和太小 → 左指针右移增大和
else:
hi -= 1 # 和太大 → 右指针左移减小和
return []
# 2. 盛最多水的容器(LeetCode 11):面积 = 短板高度 × 宽度,永远移动短板一侧
# 关键推理:若 h[l] < h[r],固定 l 时任何其他右端点都更矮更窄,最优解不可能在 l 侧丢失 → 移动短板
def max_area(height):
# S = min(h[l], h[r]) * (r - l);永远移动短板一侧
lo, hi = 0, len(height) - 1 # 双指针从两端向中间夹逼
best = 0 # 记录最大面积
while lo < hi:
h = min(height[lo], height[hi]) # 容量受短板高度限制
best = max(best, h * (hi - lo)) # 宽度 = 两柱间距
if height[lo] < height[hi]:
lo += 1 # 左板更矮 → 移动左指针找更高的板
else:
hi -= 1 # 右板更矮或相等 → 移动右指针
return best
print('two_sum_ii:', two_sum_ii([2, 7, 11, 15], 9)) # 期望 [1, 2]
print('two_sum_ii:', two_sum_ii([2, 3, 4], 6)) # 期望 [1, 3]
print('max_area:', max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 期望 49
print('max_area:', max_area([1, 1])) # 期望 1
two_sum_ii: [1, 2] two_sum_ii: [1, 3] max_area: 49 max_area: 1
§3 接雨水(LeetCode 42):双指针公式推导¶
题目:每个位置能接多少雨水。
核心公式:位置 $i$ 的储水量由两侧最高柱子的短板决定:
$$\text{water}(i) = \max\left(0,\ \min(L_{max}(i),\ R_{max}(i)) - h_i\right)$$
其中 $L_{max}(i) = \max_{j \le i} h_j$,$R_{max}(i) = \max_{j \ge i} h_j$。
朴素做法:预处理 $L_{max}$、$R_{max}$ 两个数组,时间/空间 $O(n)$。
双指针优化到 $O(1)$ 空间:
- 左右指针夹逼,维护当前扫描过的 $\text{left\_max}$ 与 $\text{right\_max}$
- 关键推理:当 $h_{lo} < h_{hi}$ 时,右侧存在高度 $\ge h_{hi}$ 的墙,所以 $R_{max}(lo) \ge h_{hi} > h_{lo}$。此时 $\min(L_{max}, R_{max}) = L_{max}$ 完全由左侧已扫描部分决定——可以立刻结算 $lo$ 位置的水量
- 对称地,$h_{hi} \le h_{lo}$ 时结算 $hi$ 位置
复杂度:时间 $O(n)$,空间 $O(1)$。
👉 指路:接雨水的单调栈版见 04-栈与队列 §8「接雨水(LeetCode 42):单调栈版」,可与本节双指针的短板推理对照理解。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 42 接雨水(双指针版):统计每个位置能接的雨水总量,空间优化到 O(1)。
# 【算法思路】位置 i 的储水量 = max(0, min(L_max(i), R_max(i)) - h[i]),
# 其中 L_max / R_max 是左右两侧的最高柱。朴素做法需两个 O(n) 辅助数组;
# 双指针版在夹逼过程中只维护已扫描部分的 left_max / right_max:
# 当 h[lo] < h[hi] 时,右侧必有高度 ≥ h[hi] 的墙兜底 ⇒ R_max(lo) ≥ h[hi] > h[lo],
# 此时 min(L_max, R_max) = L_max 已由左侧扫描确定,可立刻结算 lo 位置的水量;反之结算 hi。
# 【变量含义】height=柱高数组;lo、hi=左右指针(从两端向中间夹逼);
# left_max / right_max=左右两侧已扫描到的最高柱;total=累计雨水量。
# 【循环不变量】left_max = max(h[0..lo]),right_max = max(h[hi..n-1])(各自已扫描区间内的最高柱);
# 每个位置的水量恰好被结算一次,total 恒等于已结算位置的正确水量之和。
# 【关键边界】结算方向由 h[lo] < h[hi] 决定(相等时走 else 结算右侧);
# 当前柱 ≥ 对应侧最高柱时存不住水(更新最高柱而非加水量);
# 循环条件 lo < hi;单调数组(如 [1,2,3])存水量为 0。
# 【复杂度】时间 O(n)(一次夹逼扫描);空间 O(1)(只维护两个最高柱与总量变量)。
# 另有单调栈版(见 04-栈与队列 §8),空间同为 O(1) 思路不同,可对照。
# ════════════════════════════════════════════════════════════════════════
# 3. 接雨水(LeetCode 42):双指针版——哪边矮就结算哪边,位置 i 存水量 = min(左右最高) - h[i]
# 关键推理:h[lo] < h[hi] 时右侧至少有高度 ≥ h[hi] 的墙,故 R_max(lo) ≥ h[hi] > h[lo],
# 此时 min(L_max, R_max) = L_max 已由左侧扫描确定,可以立刻结算 lo 位置的水量(空间 O(1))
def trap(height):
# water(i) = max(0, min(L_max, R_max) - h[i])
lo, hi = 0, len(height) - 1
left_max = right_max = 0 # 左右两侧已扫描到的最高柱
total = 0 # 累计雨水量
while lo < hi: # 左右指针夹逼
if height[lo] < height[hi]: # 左侧矮 → 结算左侧
# 右侧有足够高的墙兜底,L_max 已确定
if height[lo] >= left_max:
left_max = height[lo] # 自己就是最高柱,存不住水
else:
total += left_max - height[lo] # 能存的水 = L_max - 当前高度
lo += 1
else: # 右侧矮或相等 → 结算右侧
if height[hi] >= right_max:
right_max = height[hi]
else:
total += right_max - height[hi] # 能存的水 = R_max - 当前高度
hi -= 1
return total
print('test1:', trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])) # 期望 6
print('test2:', trap([4, 2, 0, 3, 2, 5])) # 期望 9
print('test3:', trap([1, 2, 3])) # 期望 0(单调,存不住水)
test1: 6 test2: 9 test3: 0
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 26 删除有序数组中的重复项:原地去重并返回新长度(前 k 项为去重结果)。
# 模板同系列:移除元素 27、移动零 283、删除排序链表重复节点 83——只是「放回」条件不同。
# 【算法思路】同向快慢指针:slow 指向「已去重区间」的末尾下标,fast 从头扫描整个数组;
# 当 nums[fast] != nums[slow](发现新值,与去重区间末尾不同)时,
# slow+1 并把新值覆盖到 nums[slow],去重区间扩一位。
# 【变量含义】nums=输入数组(原地修改,前 slow+1 项即去重结果);
# slow=已去重区间的末尾下标;fast=扫描指针;k=返回的新长度(slow+1)。
# 【循环不变量】扫描到 fast 时,nums[0..slow] 是「已扫描部分中按序去重后的结果」,
# 且 nums[slow] 恒为已扫描部分的最后一个不同值(数组有序 ⇒ 重复值必相邻)。
# 【关键边界】空数组必须提前返回 0(否则 nums[0] 越界);
# fast 从 0 开始:nums[fast] 与 nums[slow] 首轮相等(同一元素),不会误判为新值;
# 返回长度是 slow + 1(slow 是下标,长度要 +1)。
# 【复杂度】时间 O(n)(一趟扫描);空间 O(1)(原地覆盖,不申请新数组)。
# ════════════════════════════════════════════════════════════════════════
# 4. 删除有序数组中的重复项(LeetCode 26):同向快慢指针,原地去重
# 思路:slow 指向「已去重区间」末尾,fast 扫描;遇到新值就放到 slow+1 处并推进 slow
# 为什么成立:数组有序,重复值必相邻,nums[slow] 永远是已扫描部分的最后一个不同值
def remove_duplicates(nums):
if not nums:
return 0 # 空数组直接返回 0
slow = 0 # 慢指针:已去重区间的末尾下标
for fast in range(len(nums)): # 快指针扫描整个数组
if nums[fast] != nums[slow]: # 发现新值(与去重区间末尾不同)
slow += 1 # 去重区间扩一位
nums[slow] = nums[fast] # 把新值放到 slow 位置(原地覆盖)
return slow + 1 # 新长度 = slow + 1
nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k = remove_duplicates(nums)
print('新长度 =', k, ',去重后前 k 项 =', nums[:k]) # 期望 [0,1,2,3,4]
print('空数组:', remove_duplicates([])) # 期望 0
新长度 = 5 ,去重后前 k 项 = [0, 1, 2, 3, 4] 空数组: 0
§5 滑动窗口:万能模板(背这个)¶
四要素¶
- 右扩:
right每轮 +1,把新元素纳入窗口 - 收缩:while 不满足窗口约束时,移除
left元素、left+1 - 更新答案:窗口合法时更新(通常取最大/最小)
- 状态结构:哈希表/计数器维护窗口内容
复杂度证明(为什么是 $O(n)$ 而不是 $O(n^2)$)¶
每个元素恰好进窗口一次、出窗口一次:
$$\sum_{right} O(1) + \sum_{left} O(1) = O(n)$$
左指针最多移动 $n$ 次(单调不减),整体线性。
两种「求答案」取向¶
- 最长类(无重复最长子串):窗口合法时尝试扩展,记录最大长度
- 最短类(最小覆盖子串):窗口合法时尝试收缩,记录最小长度
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】给出滑动窗口的「万能骨架」模板(四要素),并实现一个具体的固定窗口示例
# (长度为 k 的窗口内最大元素和),验证模板的通用性与复杂度结论。
# 【算法思路】四要素:① 状态结构(哈希表/计数器维护窗口内容);② 右扩:每轮把新元素纳入窗口;
# ③ 收缩:while 窗口不满足约束时移出左端元素、left+1;④ 更新答案:窗口合法时记录。
# 复杂度 O(n) 的关键:每个元素恰好进窗口一次、出窗口一次,左右指针各自单调移动。
# 固定窗口与可变窗口的区别:长度固定 → 按 right-left+1 与 k 的关系增删即可,无需 while 收缩。
# 【变量含义】data=输入序列;n=长度;left / right=窗口左右边界;window=窗口内容的状态结构;
# answer=答案(更新逻辑由题目定义);add / remove / valid / update=四个「钩子」函数;
# max_window_sum 中:s=当前窗口和;best=最大和(float('-inf') 哨兵);k=固定窗口长度。
# 【循环不变量】滑动的每一步之后,窗口 [left, right] 都满足题目约束(收缩循环保证);
# answer 恒为「所有已遍历窗口」中的最优值。
# 【关键边界】右指针 right 每轮必 +1(主循环);收缩用 while 而非 if(可能连移多元素);
# 固定窗口示例中:right-left+1 > k 才收缩,right-left+1 == k 才更新答案;
# remove 钩子里计数归 0 要 del 键(避免残留 0 计数导致状态比较误判)。
# 【复杂度】时间 O(n)(左右指针各最多移动 n 次);空间 O(1)(固定窗口和)或 O(状态结构大小)。
# ════════════════════════════════════════════════════════════════════════
# 滑动窗口通用骨架(四要素模板)——背熟即可套用所有窗口题
# 四要素:① 状态结构 ② 右扩纳入新元素 ③ 收缩左边界直到窗口合法 ④ 在合法时更新答案
def sliding_window_template(data):
n = len(data)
left = 0 # 窗口左边界
window = {} # 1. 状态结构:哈希表记录窗口内容
answer = None # 答案(初值与更新逻辑由具体题目定义)
for right in range(n): # 右指针每轮向右扩展一步
add(data[right], window) # 2. 右扩:纳入新元素
while not valid(window): # 3. 收缩:直到窗口重新合法
remove(data[left], window)
left += 1 # 左边界右移,窗口变短
answer = update(answer, left, right) # 4. 更新答案
return answer
# 下面四个辅助函数是「钩子」,由具体题目实现:add 纳入、remove 移出、valid 判合法、update 更新答案
def add(x, w): w[x] = w.get(x, 0) + 1 # 加入元素:计数 +1(不存在则从 0 开始)
def remove(x, w):
w[x] -= 1 # 移出元素:计数 -1
if w[x] == 0:
del w[x] # 计数归 0 就删除键,保持状态干净
def valid(w): return True # 由具体题目定义
def update(a, l, r): return a # 由具体题目定义答案更新规则
# 演示:统计长度为 3 的固定窗口内最大元素和
# 固定窗口与可变窗口的区别:长度固定 → 直接按 right-left+1 与 k 的关系增删即可,无需单调性收缩
def max_window_sum(nums, k):
left = 0 # 窗口左边界
s = 0 # 当前窗口内元素和
best = float('-inf') # 最大和(-inf 保证首个窗口也能更新答案)
for right, x in enumerate(nums): # 右指针扩展窗口
s += x # 纳入新元素
if right - left + 1 > k: # 窗口超长:收缩
s -= nums[left] # 移出左端元素
left += 1
if right - left + 1 == k: # 窗口恰好为 k:更新答案
best = max(best, s)
return best
print('固定窗口 k=3 最大和:', max_window_sum([1, 3, -1, -3, 5, 3, 6, 7], 3)) # 期望 16
固定窗口 k=3 最大和: 16
§6 题 4:无重复字符的最长子串(LeetCode 3)¶
题目:最长不含重复字符的子串长度。
思路:窗口 $[l, r)$ 内字符不重复。遇到重复字符 $c$ 时,把 $l$ 跳到「上一次出现 $c$ 的位置 + 1」。
公式:
$$\text{answer} = \max_{r}(\, r - \text{last}[s_r] \, )$$
即每次右扩,答案就是「当前右端点 − 该字符上次出现位置」的最大值(隐式完成左边界跳跃,无需显式 while)。
复杂度:时间 $O(n)$,空间 $O(|\Sigma|)$(字符集大小)。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 3 无重复字符的最长子串(最长类窗口):求不含重复字符的最长子串长度。
# 用「哈希表记字符最近下标 + 左边界跳跃」实现 O(n) 单次扫描。
# 【算法思路】last 记录每个字符最近一次出现的下标;right 逐字符右扩:
# 若 s[right] 在窗口内重复出现过(last[ch] >= left),直接把 left 跳到 last[ch]+1
# (跳跃式更新左边界,无需显式 while 收缩);每轮更新 best = max(best, right-left+1)。
# 【变量含义】s=输入字符串;last=字典(键=字符,值=最近出现下标);
# left=当前窗口左边界(无重复区间的起点);right=右指针;ch=当前字符;best=最长长度。
# 【循环不变量】每轮循环结束时,窗口 [left, right] 内字符互不重复,且 best 为已扫描前缀中的最长长度;
# last 恒为每个字符在整个字符串中的最近出现位置。
# 【关键边界】重复判断必须带 last[ch] >= left(字符出现过但在窗口左边界之外不算窗口内重复);
# 先判重复、更新 left,再更新 last[ch] = right(顺序不能反);空串返回 0。
# 【复杂度】时间 O(n)(每个字符恰好处理一次,left 跳跃只前进不后退);空间 O(字符集大小)。
# ════════════════════════════════════════════════════════════════════════
# 5. 无重复字符的最长子串(LeetCode 3,最长类窗口):哈希表记字符最近下标 + 左边界跳跃
# 遇到重复字符时不用 while 收缩,直接把 left 跳到「上次出现位置 + 1」,答案 = right - left + 1 的最大值
def length_of_longest_substring(s):
last = {} # 字符 -> 最近一次出现下标
left = 0 # 当前窗口左边界
best = 0 # 最长无重复子串长度
for right, ch in enumerate(s): # 右指针逐字符扫描
if ch in last and last[ch] >= left: # 该字符在窗口内出现过 → 产生重复
left = last[ch] + 1 # 左边界跳到重复字符之后
last[ch] = right # 更新该字符最近出现位置
best = max(best, right - left + 1) # 更新最长长度
return best
print('test1:', length_of_longest_substring('abcabcbb')) # 期望 3
print('test2:', length_of_longest_substring('bbbbb')) # 期望 1
print('test3:', length_of_longest_substring('pwwkew')) # 期望 3
print('test4:', length_of_longest_substring('')) # 期望 0
test1: 3 test2: 1 test3: 3 test4: 0
§7 题 5:最小覆盖子串(LeetCode 76,最短类窗口)¶
题目:在 $s$ 中找最短子串,包含 $t$ 的所有字符(含数量)。
思路:
need哈希表记录 $t$ 中各字符还缺多少;missing记录总缺量- 右扩纳入字符:若该字符仍缺则
missing -= 1 missing == 0时窗口覆盖 $t$ → 尝试收缩左边界求最短,同时恢复被移出字符的缺量
复杂度:$O(|s| + |t|)$ 时间,$O(|t|)$ 空间(只需记录 $t$ 的字符集)。
⚠️ 坑:
need里出现负数(窗口内字符多于需要)是正常的——只有> 0才影响missing。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 76 最小覆盖子串(最短类窗口):在 s 中找最短的、包含 t 全部字符(含数量)的子串。
# 用「欠账表 need + 总缺量 missing」判断窗口是否覆盖 t。
# 【算法思路】need = Counter(t) 记录每个字符「还差多少」(可为负数 = 窗口内多于需要);
# missing = len(t) 记录总缺量;右指针扩展窗口:纳入的字符仍有欠账则 missing-1;
# 当 missing == 0(窗口覆盖 t)时,while 收缩左边界求最短:每次更新更短候选,
# 同时把左端字符移出窗口并恢复其欠账量,一旦重新变缺(need > 0)就停止收缩。
# 【变量含义】s=主串;t=目标串;need=欠账表(Counter,可含负值);missing=还缺字符总数;
# left=窗口左边界;right=右指针;ch=当前纳入字符;
# best=(起点, 长度) 记录当前最优窗口,长度初值 float('inf') 作哨兵。
# 【循环不变量】缺失量守恒:missing = 各字符 max(0, need[c]) 之和;
# need[c] 为负表示窗口内该字符比 t 需要的更多(合法,不影响 missing);
# best 恒为「已扫描过的、覆盖 t 的窗口」中最短者。
# 【关键边界】s 或 t 为空直接返回 '';need[ch] > 0 才减 missing(负欠账不再欠);
# 收缩内必须先尝试更新 best 再移出左端字符(顺序反会漏掉候选);
# 最后 best[1] == inf 说明从未覆盖 ⇒ 返回 '';切片 s[best[0]:best[0]+best[1]] 取答案。
# 【复杂度】时间 O(|s| + |t|)(右指针 n 步 + 左指针至多 n 步);空间 O(|t| 的字符集大小)。
# ════════════════════════════════════════════════════════════════════════
# 6. 最小覆盖子串(LeetCode 76,最短类窗口):欠账表 need + 总缺量 missing
# 流程:右扩补字符直到 missing == 0(窗口覆盖 t)→ while 收缩左边界求最短,同时恢复被移出字符的缺量
from collections import Counter
def min_window(s, t):
if not s or not t:
return '' # 空串直接返回空结果
need = Counter(t) # 欠账表:t 中每个字符还差多少(可为负数=窗口内多余)
missing = len(t) # 还缺几个字符
left = 0 # 窗口左边界
best = (0, float('inf')) # (起点, 长度)
for right, ch in enumerate(s): # 右指针扩展窗口
if need[ch] > 0:
missing -= 1 # 该字符仍在欠账 → 总缺量 -1
need[ch] -= 1 # 窗口内该字符计数消耗(可为负数)
while missing == 0: # 窗口已覆盖 t,尝试收缩
if right - left + 1 < best[1]:
best = (left, right - left + 1) # 更短 → 更新最优窗口
need[s[left]] += 1 # 左端字符移出窗口
if need[s[left]] > 0:
missing += 1 # 重新变缺 → 总缺量 +1,停止收缩
left += 1
return '' if best[1] == float('inf') else s[best[0]:best[0] + best[1]]
print('test1:', repr(min_window('ADOBECODEBANC', 'ABC'))) # 期望 'BANC'
print('test2:', repr(min_window('a', 'a'))) # 期望 'a'
print('test3:', repr(min_window('a', 'aa'))) # 期望 ''
test1: 'BANC' test2: 'a' test3: ''
§8 题 6 / 题 7:最小子数组 + 字母异位词¶
题 6:长度最小的子数组(LeetCode 209)¶
题目:和 $\ge$ target 的最短连续子数组长度(全正数)。
公式(窗口和):
$$\text{sum}(l, r) = \sum_{i=l}^{r} nums_i \ge target$$
全正数 → 窗口和单调不减,右扩使和增大、左缩使和减小,滑动窗口正确。
题 7:找到字符串中所有字母异位词(LeetCode 438)¶
题目:$s$ 中所有长度为 $|p|$、且是 $p$ 的字母异位词的起始下标。
思路:固定窗口长度 $k = |p|$,维护窗口字符计数并与 $p$ 的计数比较。
复杂度:$O(n)$ 时间(计数比较是常数级 $|\Sigma|=26$),$O(1)$ 额外空间。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】两道「最短类」窗口的姐妹题:LeetCode 209 长度最小的子数组(窗口和)与
# LeetCode 438 找到字符串中所有字母异位词(固定窗口 + 计数比较)。
# 【算法思路】209:数组全正数 ⇒ 窗口和单调不减(右扩变大、左缩变小),
# 右指针扩展直到 s >= target,再 while 左缩求最短并尝试更新答案——滑动窗口正确性的前提是单调性。
# 438:固定窗口长度 k = len(p),维护窗口字符计数 window,每滑一步与 p 的计数表 target 比较,
# 相等则记录起点;计数归 0 的字符要 del 键,避免与 target 比较时误判。
# 【变量含义】209:target=目标和;nums=数组;left / right=窗口边界;s=当前窗口和;best=最短长度(inf 哨兵)。
# 438:s=主串;p=模式串;target=Counter(p);window=窗口字符计数表;
# res=异位词起点列表;k=固定窗口长度;i=右指针;c=滑出窗口的左端字符。
# 【循环不变量】209:s 恒为窗口 [left, right] 的元素和;best 为已扫描部分中满足条件的窗口最短长度;
# 438:window 恒为窗口 [i-k+1, i] 的字符计数,且与 target 键集一致(0 计数已删除)。
# 【关键边界】209:s >= target 才收缩;best 保持 inf 则返回 0(无符合条件的窗口);
# 438:固定窗口的删除时机是先判断 i >= k 再移除 s[i-k](顺序反了会漏窗口);
# 窗口起点下标 = i - k + 1(当 i >= k-1 时窗口长度才满 k)。
# 【复杂度】209:时间 O(n)(左右指针各至多 n 步)、空间 O(1);
# 438:时间 O(n)(计数比较是常数 26)、空间 O(1)(两个定长计数表)。
# ════════════════════════════════════════════════════════════════════════
# 7. 长度最小的子数组(LeetCode 209,最短类窗口):全正数 → 窗口和单调,右扩满足、收缩求最短
def min_subarray_len(target, nums):
left = 0 # 窗口左边界
s = 0 # 当前窗口和
best = float('inf') # 最短长度(inf 哨兵表示还没找到)
for right, x in enumerate(nums): # 右指针扩展窗口
s += x # 纳入新元素
while s >= target: # 窗口合法:收缩求最短
best = min(best, right - left + 1) # 记录更短的合法窗口
s -= nums[left] # 移出左端元素,让窗口变短
left += 1
return 0 if best == float('inf') else best # 没找到返回 0
print('min_subarray_len:', min_subarray_len(7, [2, 3, 1, 2, 4, 3])) # 期望 2
print('min_subarray_len:', min_subarray_len(11, [1, 1, 1, 1])) # 期望 0
# 8. 字母异位词(LeetCode 438):固定窗口长度 = |p|,比较窗口计数与 p 的计数是否相等
from collections import Counter
def find_anagrams(s, p):
target = Counter(p) # p 的字符计数表
window = Counter() # 当前窗口的字符计数表
res = [] # 收集所有起始下标
k = len(p) # 固定窗口长度
for i, ch in enumerate(s): # 右指针逐字符进入窗口
window[ch] += 1 # 纳入新字符
if i >= k: # 固定窗口:移除窗口左侧字符
c = s[i - k] # 窗口左端即将滑出的字符
window[c] -= 1 # 其计数 -1
if window[c] == 0:
del window[c] # 计数归 0 删除键:避免与 target 比较时误判
if window == target: # 两表相等 → 该窗口是异位词
res.append(i - k + 1) # 记录窗口起点
return res
print('find_anagrams:', find_anagrams('cbaebabacd', 'abc')) # 期望 [0, 6]
print('find_anagrams:', find_anagrams('abab', 'ab')) # 期望 [0, 1, 2]
min_subarray_len: 2 min_subarray_len: 0 find_anagrams: [0, 6] find_anagrams: [0, 1, 2]
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 392 判断子序列:判断 s 是否为 t 的子序列(相对顺序一致即可,不必连续)。
# 子序列用「同向双指针 / DP」,与「连续子串用滑动窗口」形成对比。
# 【算法思路】双指针 i 扫 s(子序列)、j 扫 t(原串):
# 若 s[i] == t[j] 则 i 前进(匹配到一个字符);j 每轮都 +1(t 从头扫到尾);
# 循环结束时 i == len(s) 说明 s 中所有字符都按序在 t 中匹配到 → True。
# 【变量含义】s=子序列目标串;t=被检查的原串;i=指向 s 的指针;j=指向 t 的指针。
# 【循环不变量】循环到任意时刻,s[0..i-1] 已作为子序列匹配进 t[0..j-1](贪心匹配:能匹配就匹配,
# 越早匹配越不浪费后续字符,绝不漏解)。
# 【关键边界】循环条件 i < len(s) and j < len(t)(任一指针走完即停);
# 空串 s 是任何串的子序列(i=0 == len(s),直接返回 True);
# t 为空而 s 非空返回 False;匹配成功后不 break,让 j 继续走到循环自然结束。
# 【复杂度】时间 O(len(t))(j 单调走完整个 t);空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 9. 判断子序列(LeetCode 392):同向双指针——s 匹配到才前进,t 一路扫到底
def is_subsequence(s, t):
i = j = 0 # i 扫 s(子序列),j 扫 t(原串)
while i < len(s) and j < len(t): # 两指针都在范围内
if s[i] == t[j]:
i += 1 # 匹配成功才推进 s 的指针
j += 1 # t 的指针始终右移
return i == len(s) # s 全部按序匹配完
assert is_subsequence('abc', 'ahbgdc') is True
assert is_subsequence('axc', 'ahbgdc') is False
assert is_subsequence('', 'ahbgdc') is True # 空串是任何串的子序列
assert is_subsequence('abc', '') is False
print('392 is_subsequence OK')
392 is_subsequence OK
题 9:最长回文子串(LeetCode 5):中心扩展¶
题目:回文串正读反读相同;在 $s$ 中找最长的回文子串。
思路:中心扩展——每个位置都能作为回文中心,向两边同步扩展直到字符不等:
- 奇数长度回文的中心是一个字符:
(i, i) - 偶数长度回文的中心是两个字符的间隙:
(i, i + 1)
对每个中心向两侧扩展并记录最长。总中心 $2n-1$ 个、每次扩展 $O(n)$ → $O(n^2)$。
💡 Manacher 算法可优化到 $O(n)$,面试写出中心扩展即可;注意区分:回文子串(连续)用中心扩展,回文子序列用 DP。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 5 最长回文子串(中心扩展法):找出 s 中最长的回文子串。
# 面试写出中心扩展即可;Manacher 算法可优化到 O(n),属加分项。
# 【算法思路】每个位置都能作为回文中心,向两边同步扩展直到字符不等:
# 奇数长度回文的中心是一个字符 (i, i);偶数长度回文的中心是两个字符的间隙 (i, i+1)。
# 枚举所有 2n-1 个中心,从每个中心向两侧扩展并记录最长结果。
# 【变量含义】s=输入字符串;expand(l, r)=从中心 (l, r) 向两侧扩展的辅助函数;
# l / r=扩展时的左右指针(扩展结束后回文区间为 [l+1, r));
# best=记录的最长回文子串;cand=当前中心扩展出的候选回文。
# 【循环不变量】expand 返回的 s[l+1:r] 是「以 (l, r) 为中心、能扩展出的最长回文」;
# best 恒为「已枚举过的所有中心」对应的最长回文子串。
# 【关键边界】扩展循环条件 l >= 0 and r < len(s) and s[l] == s[r](任一侧越界即停);
# 返回区间是 s[l+1:r](最后一次成功扩展后再各走一步,需回退);
# 偶数中心 (i, i+1) 也要试(如 'cbbd' 的 'bb');空串 / 单字符直接返回自身。
# 【复杂度】时间 O(n²)(2n-1 个中心 × 每次扩展 O(n));空间 O(1)(只存切片结果,不计输出)。
# ════════════════════════════════════════════════════════════════════════
# 10. 最长回文子串(LeetCode 5):中心扩展——每个位置都能当回文中心,向两边同步扩展
# 奇数长度回文的中心是一个字符 (i, i);偶数长度回文的中心是两个字符的间隙 (i, i+1)
# 总中心 2n-1 个、每次扩展 O(n) → O(n²);Manacher 可优化到 O(n),面试写中心扩展即可
def longest_palindrome(s):
def expand(l, r): # 从中心 (l, r) 向两边扩展
while l >= 0 and r < len(s) and s[l] == s[r]: # 两侧字符相同就继续扩展
l -= 1
r += 1
return s[l + 1:r] # 回文区间 [l+1, r)
best = '' # 记录最长回文子串
for i in range(len(s)): # 遍历每个位置作为中心
for l, r in ((i, i), (i, i + 1)): # 奇数中心 / 偶数中心
cand = expand(l, r) # 从该中心扩展出回文
if len(cand) > len(best): # 更长则更新答案
best = cand
return best
assert longest_palindrome('babad') in ('bab', 'aba')
assert longest_palindrome('cbbd') == 'bb'
assert longest_palindrome('a') == 'a'
assert longest_palindrome('') == ''
print('5 longest_palindrome OK')
5 longest_palindrome OK
§10 复杂度总表(背熟)¶
| 套路 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 相向双指针(有序两数之和) | $O(n)$ | $O(1)$ | 单调性剪枝 |
| 相向双指针(盛水/接雨水) | $O(n)$ | $O(1)$ | 短板推理 |
| 同向快慢(去重/移动零) | $O(n)$ | $O(1)$ | 一趟原地 |
| 滑动窗口(最长类) | $O(n)$ | $O(\|\Sigma\|)$ | 右扩为主 |
| 滑动窗口(最短类) | $O(n)$ | $O(\|\Sigma\|)$ | 左缩为主 |
| 固定窗口(异位词) | $O(n)$ | $O(1)$ | 计数比较 |
为什么都是 $O(n)$:双指针/窗口的左右指针各自单调移动,总步数 $O(n)$,不存在回溯。
§11 常见 bug 与边界(面试踩坑区)¶
- while 忘写
left < right:相向指针会交叉,导致重复计算/死循环 - 窗口收缩条件写反:最短类用 while 收缩,最长类通常不用 while(跳跃式更新 left)
- 固定窗口的删除时机:先判断
i >= k再移除s[i-k],顺序错了会漏窗口 - 负数不能用滑动窗口求和:窗口和没有单调性(主题 1 的 560 题用前缀和)
- 字符计数为 0 要 del:
Counter比较时残留 0 计数字符会导致!=误判 float('inf')初始值:最短类结果判空用inf哨兵,别用-1- 移动端点而非比较端点:接雨水判断
height[lo] < height[hi]决定结算哪一侧,别写成比较后忘记移动 - 子串 vs 子序列:滑动窗口只解决连续子串问题,子序列要用 DP(主题 8)
§12 面试追问与扩展(加分项)¶
12.1 为什么相向双指针不漏解¶
每次移动排除的是一个「不可能成为最优」的子区间集合——靠的是问题内在的单调性(和的大小、短板高度)。能现场讲清这一点,比背代码加分得多。
12.2 滑动窗口 vs 前缀和 vs DP 的选择¶
- 窗口和问题 + 全正数 → 滑动窗口
- 子数组和 == k(含负数)→ 前缀和 + 哈希(560)
- 最大子数组和(可任意跨越)→ 一维 DP / Kadane(53)
12.3 变体¶
- 至多 k 个不同字符的最长子串(340)
- 替换后最长重复字符(424)——窗口内最多允许 k 个「其他字符」
- 滑动窗口 + 单调队列:滑动窗口最大值(239,主题 4)
§13 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(10 题)¶
- 1. 无重复字符的最长子串(LeetCode 3)
- 2. 长度最小的子数组(209)
- 3. 删除有序数组中的重复项(26)
- 4. 移除元素(27)
- 5. 两数之和 II(167)
- 6. 验证回文串(125)
- 7. 反转字符串(344)
- 8. 移动零(283)
- 9. 反转链表(206,链表主题)
- 10. 链表的中间结点(876)
L2 进阶(10 题)¶
- 11. 最小覆盖子串(76)
- 12. 盛最多水的容器(11)
- 13. 接雨水(42)
- 14. 三数之和(15)
- 15. 四数之和(18)
- 16. 找到字符串中所有字母异位词(438)
- 17. 最长回文子串(5,中心扩展)
- 18. 字符串的排列(567)
- 19. 合并两个有序数组(88)
- 20. 有序数组的平方(977)
L3 挑战(5 题)¶
- 21. 至多包含 K 个不同字符的最长子串(340)
- 22. 替换后的最长重复字符(424)
- 23. 滑动窗口最大值(239,单调队列)
- 24. 子数组最大平均数 II(644,浮点二分 + 窗口)
- 25. 环形子数组的最大和(918)
自测要点¶
- 背写滑动窗口四要素模板(右扩/收缩/更新/状态结构)
- 讲清为什么每个元素进出窗口各一次 → 复杂度 $O(n)$
- 说出「哪些场景不能用滑动窗口」(负数、子序列)