双指针与滑动窗口
第二十三章：双指针与滑动窗口
你面对一个数组，需要找到满足某种条件的子数组或者一对元素。最朴素的想法是两层循环：外层选起点，内层选终点，逐一检查。这给出 O(n²) 的时间复杂度。当 n = 10⁶ 时，这意味着 10¹² 次操作——即使现代 CPU 每秒执行 10⁹ 次运算，也需要 1000 秒。
但如果你能利用问题本身的结构——比如数组有序、比如窗口满足单调性——你就可以让两个指针协作，把 O(n²) 降到 O(n)。这不是魔法，而是对问题性质的深刻理解所带来的算法优化。
双指针（Two Pointers）和滑动窗口（Sliding Window）是同一思想的两种表现形式：用两个指针维护一个"有意义的区间"，通过指针的移动规则保证不遗漏任何可能的最优解，同时避免重复计算。这两个技术在面试中出现的频率极高——LeetCode 上标记为"双指针"或"滑动窗口"的题目超过 200 道，几乎每一轮算法面试都会涉及。
本章将系统地讲解双指针的三种模式和滑动窗口的通用模板，从直觉到数学证明，从模板代码到边界陷阱，帮助你真正掌握这一核心技巧。
Level 1 · 你需要知道的
1.1 双指针的三种模式
双指针技术根据两个指针的移动方向和速度，可以分为三种基本模式：
| 模式 | 指针关系 | 典型场景 | 时间复杂度 |
|---|---|---|---|
| 快慢指针 | 同方向、不同速度 | 链表环检测、找中点 | O(n) |
| 对撞指针 | 相向而行 | 有序数组两数之和 | O(n) |
| 同向指针（滑动窗口） | 同方向、同速度趋势 | 子串/子数组问题 | O(n) |
为什么是这三种而不是别的分类？ 因为从拓扑上看，两个指针在线性结构上只有三种本质不同的运动模式：同向同速（快慢）、同向异端（对撞）、同向同端（滑动窗口）。任何双指针问题都可以归入这三类之一。这个分类法被 Competitive Programming 社区广泛采用（参见 Steven Halim & Felix Halim, Competitive Programming 4, 2020, Chapter 8）。
1.2 快慢指针
快慢指针的核心思想是：让两个指针以不同速度遍历，利用速度差来发现结构特征。
1.2.1 链表环检测（Floyd 判圈算法）
问题：给定一个链表，判断是否有环。
朴素解法：用哈希集合记录每个访问过的节点，如果再次遇到就有环。空间 O(n)。
快慢指针解法：让慢指针每次走 1 步，快指针每次走 2 步。如果有环，快指针一定会追上慢指针；如果无环，快指针会先到达末尾。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head: ListNode) -> bool:
"""Floyd 判圈算法：检测链表是否有环
时间复杂度: O(n)
空间复杂度: O(1)
"""
if not head or not head.next:
return False
slow = head # 慢指针：每次走 1 步
fast = head # 快指针：每次走 2 步
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # 相遇，说明有环
return True
return False # fast 到达末尾，无环
为什么快指针一定能追上慢指针？ 当两个指针都进入环后，设环长为 C。每一步快指针比慢指针多走 1 步，所以它们之间的距离每步减少 1。初始距离最大为 C-1，因此最多经过 C-1 步就会相遇。这是一个简单而优美的数学事实。
1.2.2 找链表中点
def find_middle(head: ListNode) -> ListNode:
"""找链表中点（偶数长度时返回前一个中点）
当 fast 到达末尾时，slow 恰好在中点。
原理：fast 走了 slow 两倍的距离。
"""
slow = head
fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
WHY：这个技巧之所以有效，是因为当 fast 走完整个链表时，它走了 n 步（或 n-1 步），而 slow 走了 n/2 步（或 (n-1)/2 步），恰好是中点位置。这比先遍历一次计算长度再走到中间要优雅得多，尤其在归并排序链表时非常实用。
1.2.3 判断回文链表
def is_palindrome(head: ListNode) -> bool:
"""判断回文链表 - O(n) 时间 O(1) 空间
思路：找中点 → 反转后半段 → 逐一比较
"""
if not head or not head.next:
return True
# 第一步：快慢指针找中点
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# 第二步：反转后半段链表
prev = None
curr = slow.next
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# 第三步：比较前半段和反转后的后半段
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
1.3 对撞指针
对撞指针（也叫左右指针、首尾指针）从数组两端出发，向中间收缩。适用于有序数组或需要比较两端元素的场景。
1.3.1 有序数组两数之和
问题（LeetCode #167）：在有序数组中找到两个数，使它们之和等于目标值。
def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
"""有序数组两数之和 - 对撞指针
为什么有效：
- 如果 numbers[left] + numbers[right] < target，
left 右移能增大和
- 如果 numbers[left] + numbers[right] > target，
right 左移能减小和
- 有序性保证了这种调节的单调性
"""
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1] # 题目要求 1-indexed
elif current_sum < target:
left += 1
else:
right -= 1
return [] # 无解
1.3.2 三数之和
问题（LeetCode #15）：找出数组中所有和为 0 的三元组，不能包含重复。
def three_sum(nums: list[int]) -> list[list[int]]:
"""三数之和 - 排序 + 固定一个 + 对撞指针
时间复杂度: O(n²) — 外层 O(n)，内层对撞 O(n)
关键：去重逻辑
"""
nums.sort()
result = []
n = len(nums)
for i in range(n - 2):
# 去重：跳过相同的第一个数
if i > 0 and nums[i] == nums[i - 1]:
continue
# 剪枝：最小的三个数之和 > 0，后面不可能有解
if nums[i] + nums[i + 1] + nums[i + 2] > 0:
break
# 剪枝：当前数加最大的两个数 < 0，当前数太小
if nums[i] + nums[n - 2] + nums[n - 1] < 0:
continue
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
# 去重：跳过相同的第二个数和第三个数
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
去重的关键：排序后，相同的数一定相邻。对于第一个数 nums[i]，如果 nums[i] == nums[i-1]，那么以 nums[i] 开头的所有三元组已经在上一轮被找到了，所以跳过。对于第二个和第三个数，在找到一组解后，跳过所有相同的值。
1.3.3 盛水最多的容器
问题（LeetCode #11）：给定 n 条垂直线，找出哪两条线与 x 轴构成的容器能盛最多水。
def max_area(height: list[int]) -> int:
"""盛水最多的容器 - 对撞指针
关键洞察：每次移动较短的那条线。
为什么？因为如果移动较长的线，宽度减小，
而高度受限于较短线不会增大，面积只会减小。
所以移动较长线永远不会得到更优解。
"""
left, right = 0, len(height) - 1
max_water = 0
while left < right:
# 面积 = 宽 × 高（取较短的线）
width = right - left
h = min(height[left], height[right])
max_water = max(max_water, width * h)
# 移动较短的那条线
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
1.4 滑动窗口
滑动窗口是同向双指针的特殊形式：两个指针 left 和 right 都从左向右移动，维护一个 [left, right] 的窗口。窗口有两种类型：
固定窗口：窗口大小固定为 k，left 和 right 同步移动。 可变窗口：窗口大小动态变化，根据条件决定何时收缩。
1.4.1 固定窗口模板
def fixed_window(nums: list[int], k: int) -> int:
"""固定大小滑动窗口模板
应用：子数组最大/最小平均值、定长子串问题
"""
# 初始化第一个窗口
window_sum = sum(nums[:k])
max_sum = window_sum
# 窗口滑动：每次加入右边一个，移除左边一个
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
1.4.2 可变窗口模板
def variable_window(s: str) -> int:
"""可变大小滑动窗口通用模板
核心思想：
1. right 不断右移扩展窗口
2. 当窗口不满足条件时，left 右移收缩窗口
3. 在每次合法窗口时更新答案
"""
left = 0
result = 0
window_state = {} # 窗口内的状态（如字符计数）
for right in range(len(s)):
# 1. 将 s[right] 加入窗口
char = s[right]
window_state[char] = window_state.get(char, 0) + 1
# 2. 当窗口不满足条件时，收缩左边界
while not is_valid(window_state): # 根据具体问题定义
left_char = s[left]
window_state[left_char] -= 1
if window_state[left_char] == 0:
del window_state[left_char]
left += 1
# 3. 更新答案（此时窗口一定合法）
result = max(result, right - left + 1)
return result
1.4.3 无重复字符的最长子串
问题（LeetCode #3）：给定字符串，找出不含重复字符的最长子串长度。
def length_of_longest_substring(s: str) -> int:
"""无重复字符的最长子串 - 滑动窗口
窗口条件：窗口内没有重复字符
收缩时机：当新加入的字符已存在于窗口中
"""
char_index = {} # 字符 -> 最后出现的索引
left = 0
max_len = 0
for right in range(len(s)):
char = s[right]
# 如果字符已在窗口内，直接跳到重复字符的下一位
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len
优化点：这里用 char_index 记录每个字符最后出现的位置，当发现重复时，left 可以直接跳到重复字符的下一个位置，而不需要逐步收缩。这是对标准模板的一个常见优化。
1.4.4 最小覆盖子串
问题（LeetCode #76）：给定字符串 s 和 t，找出 s 中包含 t 所有字符的最小子串。
这是滑动窗口的经典难题，被称为"滑动窗口的期末考试"。
from collections import Counter
def min_window(s: str, t: str) -> str:
"""最小覆盖子串 - 滑动窗口
关键技巧：用 'formed' 变量追踪已满足的字符种类数，
避免每次都比较整个计数器。
"""
if not s or not t or len(s) < len(t):
return ""
# t 中每个字符的需求量
need = Counter(t)
# 需要满足的不同字符种类数
required = len(need)
left = 0
formed = 0 # 已满足需求的字符种类数
window_counts = {}
# (窗口长度, left, right)
ans = (float('inf'), 0, 0)
for right in range(len(s)):
# 扩展窗口：加入 s[right]
char = s[right]
window_counts[char] = window_counts.get(char, 0) + 1
# 检查当前字符是否满足了需求
if char in need and window_counts[char] == need[char]:
formed += 1
# 收缩窗口：当所有字符都满足时，尝试缩小
while formed == required:
# 更新答案
if right - left + 1 < ans[0]:
ans = (right - left + 1, left, right)
# 移除 s[left]
left_char = s[left]
window_counts[left_char] -= 1
if left_char in need and window_counts[left_char] < need[left_char]:
formed -= 1
left += 1
return "" if ans[0] == float('inf') else s[ans[1]:ans[2] + 1]
这段代码的精妙之处：用 formed 变量追踪满足条件的字符种类数，而不是每次比较两个 Counter。这将窗口条件的检查从 O(|Σ|) 降到 O(1)，其中 |Σ| 是字符集大小。
1.5 小结：何时使用哪种模式
| 问题特征 | 应选择的模式 |
|---|---|
| 链表结构 + 追赶/检测 | 快慢指针 |
| 有序数组 + 寻找配对 | 对撞指针 |
| 连续子数组/子串 + 满足某条件 | 滑动窗口 |
| 需要从两端向中间逼近 | 对撞指针 |
| 需要 O(1) 空间遍历链表 | 快慢指针 |
Level 2 · 它是怎么运行的
2.1 滑动窗口的通用模板：一个框架解决一类问题
滑动窗口问题可以抽象为一个统一的模板。理解这个模板的内在逻辑，比记住具体题目的解法更重要。
def sliding_window_template(input_data, condition_params):
"""滑动窗口万能模板 - 详细注释版
适用问题类型：
- 最长满足条件的子数组/子串（求最大）
- 最短满足条件的子数组/子串（求最小）
- 满足条件的子数组/子串的个数（求计数）
核心不变式(invariant)：
在任意时刻，[left, right] 区间要么满足要么即将满足条件。
"""
left = 0
result = 0 # 或 float('inf')，取决于求最大还是最小
# ---- 窗口状态变量 ----
# 根据问题定义，例如：
# - 字符频率计数器
# - 当前窗口和
# - 窗口内不同元素数
state = initialize_state()
for right in range(len(input_data)):
# ======== 第一步：扩展窗口 ========
# 将 input_data[right] 纳入窗口状态
update_state_add(state, input_data[right])
# ======== 第二步：收缩窗口 ========
# while 还是 if 取决于问题：
# - 求最长：用 while，确保窗口始终合法
# - 求最短：用 while，找到最短后尝试更短
# - 求个数：需要具体分析
while window_violates_condition(state, condition_params):
update_state_remove(state, input_data[left])
left += 1
# ======== 第三步：更新答案 ========
# 此时 [left, right] 是一个合法窗口
result = update_result(result, left, right)
return result
模板的变体——求最短时的差异：
def sliding_window_min_length(nums: list[int], target: int) -> int:
"""求满足条件的最短子数组 - 关键差异：
1. result 初始化为 inf
2. 在收缩循环内部更新答案（而非循环后）
3. 收缩条件是"满足"而非"违反"
"""
left = 0
current_sum = 0
min_len = float('inf')
for right in range(len(nums)):
current_sum += nums[right]
# 当条件满足时，尝试收缩以找更短的
while current_sum >= target:
min_len = min(min_len, right - left + 1) # 在内部更新！
current_sum -= nums[left]
left += 1
return min_len if min_len != float('inf') else 0
2.2 为什么滑动窗口是 O(n)：摊还分析
初学者看到滑动窗口代码中的嵌套循环（外层 for + 内层 while）时，往往会误以为时间复杂度是 O(n²)。实际上，它是 O(n) 的。证明如下：
定理：在滑动窗口算法中，left 和 right 指针各自最多移动 n 次，因此总操作数最多为 2n = O(n)。
证明：
- right 指针在外层 for 循环中从 0 移动到 n-1，共移动 n 次。
- left 指针在内层 while 循环中只会右移（left += 1），永远不会左移。
- left 的取值范围是 [0, n-1]，且只增不减，所以 left 最多移动 n-1 次。
- 内层 while 循环在所有外层迭代中累计执行的次数等于 left 的总移动次数，即最多 n-1 次。
- 因此，总操作数 = right 的移动次数 + left 的总移动次数 = n + (n-1) = 2n - 1 = O(n)。
直觉理解：把 left 和 right 想象成两个人在数轴上向右走。right 每一步都向右走一格（共走 n 步），left 可能走也可能不走，但它永远只向右走，且不超过 right，所以它也最多走 n 步。两个人加起来最多走 2n 步。
这是**摊还分析（Amortized Analysis）**的一个经典应用。虽然单次外层循环中内层可能执行多次，但把所有外层循环的内层执行次数加起来，总数是有界的。Robert Tarjan 在 1985 年的论文 "Amortized Computational Complexity" 中系统化了这种分析方法。
2.3 快慢指针数学证明：为什么一定在环内相遇
定理（Floyd 判圈）：如果链表中存在环，快指针（每次走 2 步）一定会与慢指针（每次走 1 步）在环内相遇。
证明：
设链表的非环部分长度为 a，环的长度为 C。
当慢指针刚进入环时（走了 a 步），快指针已经走了 2a 步，即在环内走了 2a - a = a 步。此时快指针在环中的位置是 a mod C。
设此时快指针在慢指针前方 d = C - (a mod C) 步处（沿着环的方向）。或者说，慢指针在快指针前方 a mod C 步处。
等价地说，快指针需要追上慢指针，它们之间的"距离"为 d（在环上的距离）。
每走一步，快指针比慢指针多走 1 步，所以距离每步减少 1。
经过 d 步后（d < C），快指针追上慢指针，两者相遇。
推论：相遇点到环入口的距离有一个优美的性质。设相遇时慢指针在环中走了 d 步，相遇点距环入口为 d 步。此时从链表头部和相遇点同时出发、每次走 1 步的两个指针，会在环入口相遇。
def detect_cycle_entry(head: ListNode) -> ListNode:
"""找到环的入口节点
数学原理：
设非环部分长 a，环长 C，相遇时慢指针在环中走了 k 步。
慢指针走了 a + k 步，快指针走了 2(a + k) 步。
快指针比慢指针多走的步数是环长的整数倍：
2(a + k) - (a + k) = a + k = mC （m 为正整数）
所以 a = mC - k = (m-1)C + (C - k)
C - k 是从相遇点到环入口的距离。
所以从头节点走 a 步 = 从相遇点走 (m-1)圈 + (C-k) 步，
两者都恰好到达环入口。
"""
if not head or not head.next:
return None
# 第一阶段：快慢指针找相遇点
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # 无环
# 第二阶段：从头和相遇点同时出发
ptr1 = head
ptr2 = slow
while ptr1 != ptr2:
ptr1 = ptr1.next
ptr2 = ptr2.next
return ptr1 # 环入口
2.4 对撞指针的正确性证明：不会错过最优解
以"有序数组两数之和"为例，证明对撞指针不会遗漏任何解。
定理：在有序数组 A[0..n-1] 中，如果存在 i* < j* 使得 A[i*] + A[j*] = target，那么对撞指针算法一定能找到这对 (i*, j*)（或者另一对同样满足条件的 (i, j)）。
证明（反证法）：
假设算法"错过"了最优解 (i*, j*)，即在算法执行过程中，left 曾经越过 i*（即 left > i*），或者 right 曾经越过 j*（即 right < j*）。
考虑第一次发生"越过"的时刻：
情况一：left 先越过 i*。这意味着在 left = i* 的某个时刻，算法执行了 left += 1。根据算法逻辑，这只在 A[left] + A[right] < target 时发生。此时 left = i*，所以 A[i*] + A[right] < target。由于这是 left 第一次越过 i*，所以此时 right >= j*。如果 right > j*，则由数组有序性 A[right] >= A[j*]，所以 A[i*] + A[right] >= A[i*] + A[j*] = target，矛盾。如果 right = j*，则 A[i*] + A[j*] < target，与前提矛盾。
情况二：right 先越过 j*。类似推理可得矛盾。
因此，算法在 left 和 right 收缩的过程中，一定会到达 left = i*, right = j* 的状态，此时发现 A[left] + A[right] = target。
这个证明的本质：对撞指针的正确性依赖于数组的有序性。有序性保证了"left 右移使和增大，right 左移使和减小"这一单调关系，而这种单调关系确保了我们在搜索过程中不会跳过任何可能的最优解。
2.5 快慢指针的执行过程可视化
让我们通过一个具体例子来理解 Floyd 判圈算法的执行过程。
考虑链表：1 → 2 → 3 → 4 → 5 → 3（环：3 → 4 → 5 → 3）
非环部分：1 → 2 → 3（长度 a = 2，节点 1, 2）
环：3 → 4 → 5 → 3（长度 C = 3）
执行过程：
| 步数 | slow 位置 | fast 位置 | 说明 |
|---|---|---|---|
| 0 | 1 | 1 | 初始 |
| 1 | 2 | 3 | slow+1, fast+2 |
| 2 | 3 | 5 | slow+1, fast+2 |
| 3 | 4 | 4 | 相遇！ |
验证：slow 走了 3 步到节点 4，fast 走了 6 步也到节点 4。相遇后，从头节点和相遇点（节点 4）各走一步：head→2, meet→5；再走一步：head→3, meet→3。相遇于节点 3，即环入口。
2.6 滑动窗口状态机模型
滑动窗口可以用一个状态机来理解其运行逻辑：
┌──────────────────────────────┐
│ │
▼ │
┌─────────┐ 扩展(right++) ┌──────────┐ 条件满足/超出 │
│ 初始 │ ──────────────→ │ 扩展中 │ ──────────────→ │
│ left=0 │ │ 更新状态 │ │
│ right=0 │ └──────────┘ │
└─────────┘ │ │
│ 条件违反 │
▼ │
┌──────────┐ │
│ 收缩中 │ ────────────────┘
│ left++ │ 条件恢复
└──────────┘
扩展阶段：right 右移，将新元素纳入窗口状态。如果窗口仍然合法，继续扩展。
收缩阶段：当窗口状态违反条件时（如出现重复字符、窗口和超过目标），left 右移收缩窗口，直到条件恢复。
更新答案的时机：
- 求最长：在每次扩展后（窗口合法时）更新
- 求最短：在收缩循环内部更新
- 求个数：在扩展后或收缩后，视具体问题而定
2.7 对撞指针在容器盛水问题中的决策过程
为什么"移动较短边"的策略是最优的？让我们从决策树的角度来分析。
在每一步，我们有两个选择：移动 left 或移动 right。当前面积为 min(h[left], h[right]) × (right - left)。
假设 h[left] < h[right]：
选择 A：移动 left
- 宽度减少 1
- 高度可能增加（如果 h[left+1] > h[left]）
- 面积有可能增大
选择 B：移动 right
- 宽度减少 1
- 高度不可能增加！因为新的高度 = min(h[left], h[right-1]) ≤ h[left]（无论 h[right-1] 多大，都受限于较短的 h[left]）
- 面积一定减小
所以选择 B 永远不可能产生更好的结果，可以安全地排除。这就是为什么我们总是移动较短边——这是一个**支配性策略（dominated strategy）**的淘汰过程。
这个论证本质上是一个贪心证明：在每一步排除那些"不可能比当前更优"的选项。这种技巧在优化问题中非常常见（参见 Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., 2022, Chapter 15 on Greedy Algorithms）。
Level 3 · 规范怎么定义的
3.1 Floyd 判圈算法的历史
Robert W. Floyd 在 1967 年的未正式发表的备忘录中首次描述了这个算法。这篇备忘录题为 "Nondeterministic Algorithms"，虽然从未以论文形式正式发表，但通过 Donald Knuth 的引用而广为人知。Knuth 在 The Art of Computer Programming Volume 2 (1969) 的练习 3.1-6 中描述了这一算法，并将其归功于 Floyd。
历史背景：Floyd 提出这个算法的动机不是链表遍历，而是伪随机数生成器的周期检测。在 1960 年代，许多计算机程序使用线性同余生成器（Linear Congruential Generator）来产生伪随机数：x_{n+1} = (a × x_n + c) mod m。这个序列最终一定会进入循环（因为状态空间有限），而检测这个循环的长度对于评估随机数生成器的质量至关重要。
Floyd 的关键洞察是：如果序列进入长度为 λ 的循环，且尾部长度为 μ，那么存在最小的 i > 0 使得 x_i = x_{2i}。这个 i 满足 μ ≤ i ≤ μ + λ。通过这个性质，只需 O(1) 额外空间就能检测循环。
其他判圈算法的比较：
| 算法 | 发明者 | 年份 | 空间 | 检测步数 |
|---|---|---|---|---|
| Floyd 判圈 | Robert Floyd | 1967 | O(1) | ≤ μ + λ |
| Brent 判圈 | Richard Brent | 1980 | O(1) | ≤ μ + λ（常数更小） |
| 哈希记录 | — | — | O(n) | ≤ μ + λ |
Richard Brent 在 1980 年发表了 "An Improved Monte Carlo Factorization Algorithm"（BIT Numerical Mathematics, 20(2):176-184），其中提出了一种改进的判圈算法。Brent 的方法让快指针以 2 的幂步长前进，实际运行中比 Floyd 快约 36%。
def brent_cycle_detection(head: ListNode) -> bool:
"""Brent 判圈算法 - 比 Floyd 快约 36%
思路：不是让两个指针同时跑，而是：
1. tortoise 固定不动
2. hare 走 1, 2, 4, 8, ... 步（倍增）
3. 如果 hare 遇到 tortoise，有环
4. 每轮结束后 tortoise 跳到 hare 位置
"""
if not head or not head.next:
return False
tortoise = head
hare = head.next
power = 1 # 当前轮次 hare 需要走的步数
steps = 1 # 当前轮次 hare 已走的步数
while hare and hare != tortoise:
if steps == power:
# 当前轮次结束，开始下一轮
tortoise = hare
power *= 2
steps = 0
hare = hare.next
steps += 1
return hare == tortoise
3.2 滑动窗口与双端队列的关系：单调队列
滑动窗口的一个重要变体是与单调队列（Monotone Queue）结合使用。在第 6 章中我们介绍了队列和双端队列的基本操作，这里展示它们在滑动窗口中的核心应用。
问题（LeetCode #239）：滑动窗口最大值。给定数组和窗口大小 k，返回每个窗口中的最大值。
朴素解法是对每个窗口位置求最大值，O(nk)。使用单调递减双端队列可以做到 O(n)。
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
"""滑动窗口最大值 - 单调递减队列
核心思想：维护一个双端队列，保证队列中的元素从队头到队尾递减。
队头始终是当前窗口的最大值。
为什么有效（引用 Adamchik & Rao, 'A O(1) Algorithm for
Implementing the LookBack Option', 2000 的思想）：
如果一个较新的元素比一个较老的元素大，那么较老的元素永远不可能
成为任何未来窗口的最大值——它可以被安全丢弃。
"""
if not nums or k == 0:
return []
dq = deque() # 存储索引，对应值单调递减
result = []
for i in range(len(nums)):
# 1. 移除过期元素（已不在窗口内的）
while dq and dq[0] <= i - k:
dq.popleft()
# 2. 维护单调性：移除所有比当前元素小的
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()
# 3. 加入当前元素
dq.append(i)
# 4. 窗口形成后，队头就是最大值
if i >= k - 1:
result.append(nums[dq[0]])
return result
摊还复杂度分析：每个元素最多入队一次、出队一次，所以所有队列操作的总次数为 O(n)。这与滑动窗口的 2n 移动证明是相同的分析思路。
单调队列的设计决策：为什么存储索引而不是值？因为我们需要判断队头元素是否已经滑出窗口（通过比较索引和当前位置的距离）。如果只存储值，就无法判断元素是否过期。这是一个看似微小但至关重要的设计选择。
3.3 双指针在排序算法中的应用
双指针思想不仅用于搜索问题，它在经典排序算法中也扮演核心角色。
3.3.1 快速排序的 Partition
快速排序的核心操作是 Partition：选一个 pivot，把数组分成"小于 pivot"和"大于 pivot"两部分。这本质上是一个对撞指针操作。
def lomuto_partition(arr: list[int], lo: int, hi: int) -> int:
"""Lomuto 分区方案 - 同向双指针
Nico Lomuto 的方案使用一个"边界指针" i：
arr[lo..i] 是 <= pivot 的部分
arr[i+1..j-1] 是 > pivot 的部分
arr[j..hi-1] 是未处理的部分
"""
pivot = arr[hi]
i = lo - 1 # 边界指针：小于等于 pivot 区域的右端
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1
def hoare_partition(arr: list[int], lo: int, hi: int) -> int:
"""Hoare 分区方案 - 对撞双指针
Tony Hoare（1962，"Quicksort", Computer Journal 5(1):10-16）
的原始方案使用左右两个指针相向扫描。
比 Lomuto 方案交换次数更少（平均少约 3 倍）。
"""
pivot = arr[lo]
i = lo - 1
j = hi + 1
while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
两种 Partition 的对比：
| 特性 | Lomuto | Hoare |
|---|---|---|
| 指针模式 | 同向（快慢） | 对撞 |
| 交换次数 | 较多 | 较少（约 1/3） |
| 适合场景 | 教学、简洁 | 实际使用、性能优先 |
| 处理重复元素 | 容易退化到 O(n²) | 相对好一些 |
Robert Sedgewick 在其博士论文 "Quicksort" (1975) 中对这两种方案进行了详尽的数学分析。
3.3.2 归并排序的 Merge
归并排序的合并（Merge）操作使用两个指针分别扫描两个有序子数组，每次取较小的放入结果。
def merge(arr: list[int], left: int, mid: int, right: int) -> None:
"""归并操作 - 经典双指针合并两个有序数组
John von Neumann, 1945 年首次描述归并排序。
合并操作的正确性来自：
两个子数组各自有序 → 每个子数组的第一个元素是该子数组的最小值
→ 两个"最小值"中较小的就是全局最小值
"""
temp = arr[left:right + 1]
i = 0 # 指向左半部分的起始
j = mid - left + 1 # 指向右半部分的起始
k = left # 写入位置
left_end = mid - left # 左半部分的结尾（在 temp 中的索引）
right_end = right - left # 右半部分的结尾
while i <= left_end and j <= right_end:
if temp[i] <= temp[j]: # 注意 <=：保持稳定性
arr[k] = temp[i]
i += 1
else:
arr[k] = temp[j]
j += 1
k += 1
# 拷贝剩余元素
while i <= left_end:
arr[k] = temp[i]
i += 1
k += 1
while j <= right_end:
arr[k] = temp[j]
j += 1
k += 1
3.3.3 荷兰国旗问题（三路 Partition）
Edsger Dijkstra 在 1976 年的 A Discipline of Programming 中提出了"荷兰国旗问题"：将数组中的元素按三种类别（红、白、蓝，对应 0、1、2）排序，要求一次遍历完成。
这需要三个指针：
def sort_colors(nums: list[int]) -> None:
"""荷兰国旗问题 / 三路快排 partition
三个指针的含义：
- [0, low): 全是 0（红色）
- [low, mid): 全是 1（白色）
- [mid, high]: 未处理
- (high, n-1]: 全是 2（蓝色）
不变式：始终维护以上四个区间的正确性
"""
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else: # nums[mid] == 2
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
# 注意：mid 不动，因为从 high 换来的可能是 0
3.4 双指针与不变式（Loop Invariant）
循环不变式是理解和证明双指针算法正确性的核心工具。David Gries 在 The Science of Programming (1981) 中系统化了这一方法论。
对于每个双指针算法，我们需要明确：
- 初始化（Initialization）：循环开始前，不变式成立。
- 保持（Maintenance）：如果某次迭代开始前不变式成立，那么该次迭代结束后不变式仍然成立。
- 终止（Termination）：循环终止时，不变式加上终止条件给出我们想要的结论。
以对撞指针解决两数之和为例：
不变式：如果存在解 (i*, j*) 满足 A[i*] + A[j*] = target，则在任何时刻 left ≤ i* 且 right ≥ j*。
- 初始化：left = 0 ≤ i*，right = n-1 ≥ j*。成立。
- 保持：如果 A[left] + A[right] < target，我们让 left++。需要证明新的 left ≤ i*。如果 left = i*，则 A[i*] + A[right] < target，而 right ≥ j*，所以 A[i*] + A[right] ≥ A[i*] + A[j*] = target，矛盾。所以 left < i*，即 left++ 后仍然 ≤ i*。右移 right 的情况类似。
- 终止：当 left = i*, right = j* 时，A[left] + A[right] = target，算法返回解。
3.5 学术脉络：双指针的理论基础
双指针技术的理论基础横跨多个领域：
搜索理论：对撞指针本质上是一种在有序空间中的高效搜索。它与二分查找共享相同的"每步排除一部分搜索空间"的思想，只是排除的方式不同。John Bentley 在 Programming Pearls (1986) 中大量使用了这种技巧。
在线算法：滑动窗口是在线算法（Online Algorithm）的一种形式——数据以流的方式到达，我们需要在有限内存中维护某些统计量。这与流式算法（Streaming Algorithms）有密切联系，后者由 Alon, Matias & Szegedy 在 "The Space Complexity of Approximating the Frequency Moments" (1996, 获得 Gödel Prize) 中系统化。
摊还分析：滑动窗口的 O(n) 复杂度分析是摊还分析的教科书案例。这一技术由 Robert Tarjan 在 "Amortized Computational Complexity" (SIAM Journal on Algebraic and Discrete Methods, 6(2):306-318, 1985) 中正式定义。
Level 4 · 边界与陷阱
4.1 常见边界错误
4.1.1 Off-by-one 错误
Off-by-one 是双指针中最常见的 bug 来源。以下是几个典型的错误点：
错误 1：循环条件写错
# 错误：用 left <= right 还是 left < right？
def two_sum_sorted_wrong(nums, target):
left, right = 0, len(nums) - 1
while left <= right: # 错误！当 left == right 时，是同一个元素
if nums[left] + nums[right] == target:
return [left, right]
...
# 正确：题目要求两个不同的元素
def two_sum_sorted_correct(nums, target):
left, right = 0, len(nums) - 1
while left < right: # 正确
...
错误 2：窗口大小计算
# 窗口 [left, right] 的长度是 right - left + 1（闭区间）
# 窗口 [left, right) 的长度是 right - left（左闭右开）
# 搞混这两者是最常见的 off-by-one 错误
# 例：找中点
n = len(arr)
mid = n // 2 # 对于偶数长度，这是右中点
mid = (n - 1) // 2 # 这是左中点
错误 3：快慢指针的初始位置
# 找中点：根据需要"前中点"还是"后中点"，初始化和循环条件不同
# 前中点（对于 1→2→3→4，返回 2）
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# 后中点（对于 1→2→3→4，返回 3）
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
4.1.2 空数组和边界情况
def safe_two_pointer(nums: list[int]) -> int:
"""安全的双指针模板 - 处理所有边界"""
# 边界检查：空数组
if not nums:
return 0 # 或者抛出异常，取决于题目要求
# 边界检查：单元素数组
if len(nums) == 1:
return nums[0] # 很多双指针算法对单元素有特殊处理
left, right = 0, len(nums) - 1
# ... 主逻辑
4.1.3 全相同元素
当数组中所有元素相同时，很多双指针算法会出现意外行为：
# 三数之和中，如果数组是 [0, 0, 0, 0, 0]
# 不正确的去重可能导致重复答案或漏解
# 错误写法：在移动前去重
while left < right and nums[left] == nums[left + 1]: # 可能 left+1 越界！
left += 1
# 正确写法：在找到解之后再去重，并确保边界
if total == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
4.2 滑动窗口中字符计数的陷阱
4.2.1 Counter vs dict：看似等价，实则有坑
Python 的 collections.Counter 和普通 dict 在滑动窗口中行为不同：
from collections import Counter
# Counter 的特殊行为：允许负数计数
c = Counter()
c['a'] -= 1
print(c['a']) # -1
print(c) # Counter({'a': -1}) -- 注意！不会删除
# 普通 dict
d = {}
d['a'] = d.get('a', 0) - 1
print(d['a']) # -1
# 但 'a' in d 为 True，即使值为负
# 陷阱：用 len(counter) 判断"有多少不同字符在窗口中"
c = Counter()
c['a'] += 1
c['a'] -= 1
print(len(c)) # 1！因为 Counter 不会自动删除计数为 0 的键
# 正确做法：手动删除
if c['a'] == 0:
del c['a']
建议：在滑动窗口问题中，优先使用普通 dict 并手动维护删除逻辑，避免 Counter 的隐式行为带来的 bug。
def safe_window_counter():
"""安全的窗口计数器操作模板"""
window = {}
# 添加
def add(char):
window[char] = window.get(char, 0) + 1
# 移除
def remove(char):
window[char] -= 1
if window[char] == 0:
del window[char] # 关键：计数为 0 时删除
# 判断窗口是否包含某字符
def contains(char):
return char in window # 此时 "in" 语义正确
4.2.2 比较两个计数器的陷阱
在"最小覆盖子串"类问题中，需要判断窗口是否覆盖了目标。
# 错误做法：每次都比较整个计数器
# 时间复杂度 O(|Σ|)，|Σ| 为字符集大小
def is_covered_slow(window, need):
for char, count in need.items():
if window.get(char, 0) < count:
return False
return True
# 正确做法：维护一个 formed 变量，O(1) 判断
# 见 1.4.4 节的最小覆盖子串代码
4.2.3 Unicode 和多字节字符
在实际工程中（虽然面试中少见），需要注意 Python 3 的字符串是 Unicode 字符序列，每个"字符"可能由多个码位组成（如 emoji、组合字符）：
# Python 3 中每个索引位置是一个 Unicode 码位
s = "café"
print(len(s)) # 4（正常）
s = "👨👩👧👦" # 家庭 emoji
print(len(s)) # 11（由多个码位组合而成！）
# 面试中通常假设 ASCII，但实际工程需要注意
4.3 面试高频题详解
4.3.1 长度最小的子数组（LeetCode #209）
问题：给定正整数数组和目标值 target，找到和 ≥ target 的最短子数组长度。
def min_sub_array_len(target: int, nums: list[int]) -> int:
"""长度最小的子数组 - 可变滑动窗口（求最短）
关键条件：数组元素都是正整数！
这保证了"右移 left 一定减小窗口和"的单调性。
如果有负数，这个方法就不适用了。
"""
left = 0
current_sum = 0
min_len = float('inf')
for right in range(len(nums)):
current_sum += nums[right]
# 当和 >= target 时，尝试收缩
while current_sum >= target:
min_len = min(min_len, right - left + 1)
current_sum -= nums[left]
left += 1
return min_len if min_len != float('inf') else 0
# 测试
assert min_sub_array_len(7, [2, 3, 1, 2, 4, 3]) == 2 # [4, 3]
assert min_sub_array_len(4, [1, 4, 4]) == 1 # [4]
assert min_sub_array_len(11, [1, 1, 1, 1, 1]) == 0 # 无解
为什么必须是正整数？ 如果数组中有负数，移除左边的元素不一定减小窗口和，单调性被破坏，滑动窗口就不适用了。含负数的情况需要用前缀和 + 有序集合（O(n log n)）或者其他方法。
4.3.2 找到字符串中所有字母异位词（LeetCode #438）
问题：在字符串 s 中找到所有 p 的字母异位词（排列），返回它们的起始索引。
from collections import Counter
def find_anagrams(s: str, p: str) -> list[int]:
"""字母异位词 - 固定窗口 + 字符计数
核心洞察：这是一个固定大小（len(p)）的滑动窗口问题。
窗口中的字符频率与 p 相同时，就是一个异位词。
优化：不是每次比较整个频率表，
而是维护一个 'matches' 变量记录匹配的字符数。
"""
if len(s) < len(p):
return []
result = []
p_count = Counter(p)
s_count = Counter()
# 26 个字母中，有多少种字符的频率已经匹配
matches = 0
# 需要匹配的字符种类总数
target = len(p_count)
for i in range(len(s)):
# 添加右边字符
char = s[i]
s_count[char] = s_count.get(char, 0) + 1
# 检查是否新增了一个匹配
if char in p_count:
if s_count[char] == p_count[char]:
matches += 1
elif s_count[char] == p_count[char] + 1:
# 之前匹配，现在多了一个，不再匹配
matches -= 1
# 移除左边字符（窗口超过 len(p) 时）
if i >= len(p):
left_char = s[i - len(p)]
if left_char in p_count:
if s_count[left_char] == p_count[left_char]:
matches += 1 # 移除后恰好匹配了（之前多）
# 等等，这里逻辑要小心——先判断再删
elif s_count[left_char] == p_count[left_char] + 1:
# 删除前刚好多一个，删除后匹配
pass
s_count[left_char] -= 1
if left_char in p_count:
if s_count[left_char] == p_count[left_char]:
matches += 1
elif s_count[left_char] == p_count[left_char] - 1:
matches -= 1
if s_count[left_char] == 0:
del s_count[left_char]
# 所有字符频率匹配 → 是异位词
if matches == target:
result.append(i - len(p) + 1)
return result
上面的代码虽然效率高但逻辑复杂。在面试中，一个更清晰的写法：
def find_anagrams_clean(s: str, p: str) -> list[int]:
"""字母异位词 - 简洁版（面试推荐）
使用固定窗口 + 直接比较计数器。
由于字符集固定为 26 个字母，比较计数器是 O(26) = O(1)。
"""
if len(s) < len(p):
return []
p_count = [0] * 26
w_count = [0] * 26
result = []
for c in p:
p_count[ord(c) - ord('a')] += 1
for i in range(len(s)):
# 加入右边
w_count[ord(s[i]) - ord('a')] += 1
# 移除左边（维持窗口大小为 len(p)）
if i >= len(p):
w_count[ord(s[i - len(p)]) - ord('a')] -= 1
# 比较
if i >= len(p) - 1 and w_count == p_count:
result.append(i - len(p) + 1)
return result
4.3.3 替换后的最长重复字符（LeetCode #424）
问题：给定字符串 s 和整数 k，可以将字符串中的任意字符替换为其他字符，最多替换 k 次。找出替换后最长的只含一种字符的子串长度。
def character_replacement(s: str, k: int) -> int:
"""替换后最长重复字符 - 滑动窗口
关键洞察：
窗口 [left, right] 合法的条件是：
窗口长度 - 窗口中出现最多的字符次数 ≤ k
即"需要替换的字符数 ≤ k"
重要技巧：max_freq 只增不减！
这是这道题最微妙的地方。
"""
count = [0] * 26
left = 0
max_freq = 0 # 历史最大频率
max_len = 0
for right in range(len(s)):
idx = ord(s[right]) - ord('A')
count[idx] += 1
max_freq = max(max_freq, count[idx])
# 窗口不合法：需要替换的字符数 > k
# 注意：这里用 if 而非 while！
if (right - left + 1) - max_freq > k:
count[ord(s[left]) - ord('A')] -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len
为什么 max_freq 只增不减也能给出正确答案？
这是这道题最让人困惑的地方。直觉上，当左指针右移后，窗口内最高频字符的频率可能下降，此时 max_freq 不再准确。但这不影响正确性：
- 答案只可能在
max_freq增大时更新（因为窗口要变大，需要更高的 max_freq）。 - 当
max_freq不增时，窗口不会变大（因为(right-left+1) - max_freq > k会触发收缩）。 - 所以"过时"的
max_freq只会让窗口保持当前大小不变，不会错误地增大。
这个优化将内层操作从"遍历 count 数组找最大值"（O(26)）简化为 O(1)，虽然常数改善不大，但展示了一种重要的思维方式：有时候"不精确"的变量反而能简化算法，只要它不影响最终答案的正确性。
4.4 三数之和去重的正确写法
三数之和的去重逻辑是面试中最容易出错的地方。让我们详细分析每一种错误：
def three_sum_dedup_analysis(nums: list[int]) -> list[list[int]]:
"""三数之和 - 去重的所有坑"""
nums.sort()
result = []
for i in range(len(nums) - 2):
# ============ 第一层去重 ============
# 错误写法 1：
# if nums[i] == nums[i + 1]: continue
# 这会跳过 [-1, -1, 2] 这种合法答案！
# 正确写法：与前一个比较而非后一个
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
# ============ 第二层去重 ============
# 错误写法 2：只跳过 left 不跳过 right
# 可能遗漏 right 侧的重复
# 错误写法 3：先 left+=1 再去重
# left += 1
# while left < right and nums[left] == nums[left - 1]:
# left += 1
# 这样写是对的！但很多人会写成下面的错误形式：
# 错误写法 4：去重边界不检查
# while nums[left] == nums[left + 1]: # left+1 可能越界！
# left += 1
# 正确且安全的去重：
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1 # 移动到下一个不同的值
right -= 1 # 移动到下一个不同的值
elif total < 0:
left += 1
else:
right -= 1
return result
总结去重原则：
- 对第一个数：与前一个比较（
nums[i] == nums[i-1]），不是后一个 - 对第二、三个数：在找到解之后跳过重复值
- 所有去重循环都必须检查
left < right防止越界
4.5 什么时候不能用双指针
双指针不是万能的。明确它的适用条件，才能避免在错误的问题上浪费时间。
4.5.1 无序数组的两数之和
经典的 Two Sum（LeetCode #1）：在无序数组中找两个数使和为 target。
为什么对撞指针不行？ 对撞指针的正确性依赖于数组有序——这保证了"left 右移增大和，right 左移减小和"的单调性。无序数组不具备这个性质。
为什么排序后用对撞指针也不行？ 可以找到满足条件的两个值，但题目要求返回原始索引。排序破坏了索引信息。
正确做法：哈希表 O(n) 或排序 + 对撞指针 + 记录原始索引。
# 无序两数之和：哈希表是最佳解法
def two_sum_unsorted(nums: list[int], target: int) -> list[int]:
seen = {} # 值 -> 索引
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
4.5.2 不满足单调性条件的滑动窗口
滑动窗口要求：当窗口不满足条件时，收缩左边界一定能使窗口"趋向"满足条件。换言之，要求窗口条件具有单调性：
- 扩展窗口（right 右移）使条件"更容易违反"
- 收缩窗口（left 右移）使条件"更容易满足"
反例：含负数的子数组和问题
# 问题：找和 >= target 的最短子数组，数组可能有负数
# 例：nums = [2, -1, 2], target = 3
#
# 滑动窗口失败：
# right=0: sum=2 < 3, 继续
# right=1: sum=1 < 3, 继续
# right=2: sum=3 >= 3, 找到 [2,-1,2] 长度 3
# 收缩：left=1, sum=1 < 3, 停止
# 答案：3
#
# 但正确答案是什么？ 还是 3，这个例子恰好对了。
# 但考虑 nums = [1, -1, 5, -2, 3], target = 3
# 滑动窗口会给出 [1, -1, 5] 长度 3
# 但 [5] 长度 1 就满足了！
# 收缩时 left 从 0 到 1：sum = -1+5-2+3=5 >= 3...
# 这个例子中其实也能找到，但构造特定情况是可以让它失败的。
# 含负数情况的正确解法：前缀和 + 有序数据结构
4.5.3 需要考虑所有子集而非子数组的问题
双指针/滑动窗口只能处理连续子数组/子串问题。如果问题问的是"任意子集"（不要求连续），双指针就不适用了。
例如："从数组中选择若干元素使得和为 target"——这是一个子集和问题（NP-Complete 的变体），需要动态规划或回溯。
4.6 实战中的性能陷阱
4.6.1 Python 中的字符串拼接
# 错误：在滑动窗口中用字符串拼接构建子串
result = ""
for right in range(len(s)):
result += s[right] # O(n) 拷贝！总复杂度 O(n²)
# 正确：用索引记录，最后切片
# 只在需要时 s[best_left:best_right+1]
4.6.2 频繁的列表 pop(0)
# 错误：用 list 模拟滑动窗口
window = []
window.append(x) # O(1)
window.pop(0) # O(n)！列表的 pop(0) 需要移动所有元素
# 正确：用 deque 或只用索引
from collections import deque
window = deque()
window.append(x) # O(1)
window.popleft() # O(1)
4.6.3 defaultdict 的隐式创建
from collections import defaultdict
# 陷阱：in 操作符不会触发默认值创建
# 但直接访问会！
d = defaultdict(int)
if d['x']: # 这会创建 d['x'] = 0 ！
pass
print(len(d)) # 1，而非 0
# 在滑动窗口中，这可能影响 len(window) 的判断
# 安全做法：用 d.get('x', 0) 或先 if 'x' in d
4.7 进阶：双指针的组合变体
4.7.1 多指针问题：四数之和
def four_sum(nums: list[int], target: int) -> list[list[int]]:
"""四数之和 - 排序 + 两层循环 + 对撞指针
时间复杂度: O(n³)
泛化：k 数之和可以用递归 + 对撞指针实现，O(n^(k-1))
"""
nums.sort()
result = []
n = len(nums)
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue
# 剪枝
if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
break
if nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target:
continue
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# 剪枝
if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
break
if nums[i] + nums[j] + nums[n-2] + nums[n-1] < target:
continue
left, right = j + 1, n - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total == target:
result.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < target:
left += 1
else:
right -= 1
return result
4.7.2 滑动窗口 + 哈希表：子数组计数问题
问题（LeetCode #992）：K 个不同整数的子数组数。
这道题展示了一个重要技巧："恰好 K 个" = "至多 K 个" - "至多 K-1 个"。
def subarrays_with_k_distinct(nums: list[int], k: int) -> int:
"""K 个不同整数的子数组 - 双滑动窗口
直接求"恰好 K 个"很难，因为滑动窗口天然适合求"至多"。
技巧：exactly(K) = atMost(K) - atMost(K-1)
"""
def at_most(k: int) -> int:
"""至多 k 个不同整数的子数组数"""
count = {}
left = 0
result = 0
for right in range(len(nums)):
count[nums[right]] = count.get(nums[right], 0) + 1
while len(count) > k:
count[nums[left]] -= 1
if count[nums[left]] == 0:
del count[nums[left]]
left += 1
# 以 right 结尾的合法子数组数 = right - left + 1
result += right - left + 1
return result
return at_most(k) - at_most(k - 1)
为什么 right - left + 1 是以 right 结尾的合法子数组数？ 当窗口 [left, right] 满足"至多 K 个不同整数"时，所有以 right 结尾、起点在 [left, right] 之间的子数组也都满足条件（因为缩小窗口只会减少不同整数数）。这样的子数组共有 right - left + 1 个。
4.7.3 双指针 + 二分搜索
有些问题结合了双指针和二分搜索。例如：
问题：在有序矩阵中搜索（LeetCode #240），矩阵每行每列都有序。
def search_matrix(matrix: list[list[int]], target: int) -> bool:
"""有序矩阵搜索 - 从右上角出发的双指针
从右上角出发：
- 当前值 > target：左移（排除当前列）
- 当前值 < target：下移（排除当前行）
- 当前值 == target：找到
这本质上是在 2D 有序空间上的对撞指针。
"""
if not matrix or not matrix[0]:
return False
rows, cols = len(matrix), len(matrix[0])
row, col = 0, cols - 1 # 从右上角出发
while row < rows and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
col -= 1
else:
row += 1
return False
4.8 面试策略总结
在面试中遇到双指针/滑动窗口问题时，按以下步骤思考：
第一步：识别问题类型
- 涉及链表 → 考虑快慢指针
- 有序数组 + 寻找配对 → 对撞指针
- 连续子数组/子串 + 条件限制 → 滑动窗口
- "最长/最短满足条件的..." → 几乎一定是滑动窗口
第二步：确认单调性
- 扩展窗口是否使条件更容易/更难满足？
- 收缩窗口是否使条件反向变化？
- 如果两个方向都不确定，滑动窗口可能不适用
第三步：选择模板
- 求最长 → right 主动扩展，违反条件时收缩，收缩后更新答案
- 求最短 → right 主动扩展，满足条件时更新答案并收缩
- 求个数 → 通常使用"至多 K"减法技巧
第四步：处理边界
- 空输入
- 全相同元素
- 无解情况
- 去重逻辑
第五步：验证复杂度
- 确认 left 和 right 各最多移动 n 次
- 确认窗口内操作是 O(1) 或 O(|Σ|)
本章总结
双指针和滑动窗口是从暴力 O(n²) 到优雅 O(n) 的一次思维跃迁。它们的本质是：利用问题的结构性（有序性、单调性）来安全地排除搜索空间，让两个指针的协作取代嵌套循环的穷举。
核心要点回顾：
| 技术 | 适用条件 | 复杂度 | 关键证明 |
|---|---|---|---|
| 快慢指针 | 链表、环检测 | O(n) 时间 O(1) 空间 | 速度差 → 一定追上 |
| 对撞指针 | 有序数组、配对搜索 | O(n) | 单调性 → 不遗漏 |
| 滑动窗口 | 连续子数组/子串 | O(n)（摊还） | left/right 各移 n 次 |
掌握这三种模式及其变体，你将能够解决算法面试中约 15-20% 的数组/字符串问题。更重要的是，理解它们背后的数学证明和适用条件，能帮助你在遇到新问题时快速判断是否可以用双指针，而不是盲目套模板。
下一章我们将讨论贪心算法——另一种通过局部最优选择达到全局最优的策略，它与双指针中"移动较短边"的贪心决策有着深刻的联系。