02 · 双指针与滑动窗口
来源： labuladong 双指针框架 + 滑动窗口”三问法” + 代码随想录双指针专题
核心价值： 将 O(n²) 暴力解优化到 O(n)
一、本质理解
双指针的核心思想是 利用两个指针的相对运动来减少搜索空间。
labuladong 的双指针分类：
双指针
├── 左右指针（对撞）：两端向中间移动 → 有序数组、回文串
├── 快慢指针（同向）：一快一慢 → 链表判环、找中点
└── 滑动窗口（同向）：维护一个区间 → 子串/子数组问题
延伸理解： 滑动窗口本质上是 快慢指针的一种特殊形式，特殊在窗口内的元素始终是连续的（子数组/子串）。
二、对撞指针（左右指针）
核心思路
两个指针分别从数组的两端出发，向中间移动，直到相遇。
适用条件： 数组通常是有序的（或经过排序处理）。
标准模板
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target:
return [left, right]
elif s < target:
left += 1 # 和太小，左指针右移
else:
right -= 1 # 和太大，右指针左移
return []三数之和（排序 + 对撞指针）
def three_sum(nums):
nums.sort()
n = len(nums)
res = []
for i in range(n - 2):
# 去重：跳过重复的固定元素
if i > 0 and nums[i] == nums[i - 1]:
continue
# 双指针找两数之和
left, right = i + 1, n - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
res.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
# 去重：跳过重复元素
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif s < 0:
left += 1
else:
right -= 1
return res三、快慢指针
核心思路
两个指针从同一起点出发，一个走的快（如每次 2 步），一个走的慢（如每次 1 步）。
模板 1：链表判环
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False模板 2：找环入口（Floyd 算法）
def detect_cycle(head):
slow = fast = head
# 第一阶段：快慢指针相遇
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else: # 无环
return None
# 第二阶段：头指针和慢指针同步走，相遇点即为入口
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow模板 3：找链表中点
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # 偶数长度时返回偏右的中点四、滑动窗口 ⭐（高频核心）
labuladong 三问判断法
滑动窗口的核心是 三个问题：
问题一：什么时候扩大窗口？
→ 当前窗口还不满足"可行解"条件时，右指针右移扩大
问题二：什么时候缩小窗口？
→ 当前窗口已经满足"可行解"条件时，左指针右移缩小
问题三：什么时候更新答案？
→ 缩小窗口时（求最小）或扩大窗口时（求最大）
通用模板
from collections import defaultdict
def sliding_window(s):
left, right = 0, 0
window = defaultdict(int) # 窗口内元素统计
# need = ... # 目标条件（看题目需要）
while right < len(s):
# 扩大窗口：右指针右移
c = s[right]
right += 1
window[c] += 1
# ... 更新窗口数据 ...
# 缩小窗口：当窗口满足条件时
while "窗口需要缩小":
d = s[left]
left += 1
window[d] -= 1
if window[d] == 0:
del window[d]
# ... 更新窗口数据 ...
return result模板应用：无重复字符的最长子串
def length_of_longest_substring(s):
window = defaultdict(int)
left = right = 0
max_len = 0
while right < len(s):
c = s[right]
right += 1
window[c] += 1
# 出现重复字符，缩小窗口
while window[c] > 1:
d = s[left]
left += 1
window[d] -= 1
# 扩大窗口时更新答案（求最大）
max_len = max(max_len, right - left)
return max_len模板应用：最小覆盖子串
from collections import defaultdict
def min_window(s, t):
need = defaultdict(int)
window = defaultdict(int)
for c in t:
need[c] += 1
left = right = 0
valid = 0 # 已满足需求的字符种类数
start, length = 0, float('inf')
while right < len(s):
c = s[right]
right += 1
if c in need:
window[c] += 1
if window[c] == need[c]:
valid += 1
# 所有字符都已覆盖，开始收缩
while valid == len(need):
# 缩小窗口时更新答案（求最小）
if right - left < length:
start = left
length = right - left
d = s[left]
left += 1
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
return s[start:start + length] if length != float('inf') else ""五、Hot 100 双指针/滑动窗口题目清单
双指针（对撞）
| 题号 | 题目 | 难度 | 核心思路 | 建议用时 |
|---|---|---|---|---|
| 283 | 移动零 | Easy | 快慢指针，非零前移 | 25 min |
| 11 | 盛最多水的容器 | Medium | 对撞指针，移动较短的 | 30 min |
| 15 | 三数之和 | Medium | 排序 + 对撞指针 + 去重 | 40 min |
| 42 | 接雨水 | Hard | 对撞指针，维护左右最大高 | 40 min |
滑动窗口
| 题号 | 题目 | 难度 | 核心思路 | 建议用时 |
|---|---|---|---|---|
| 3 | 无重复最长子串 | Medium | 滑动窗口 + 哈希集 | 30 min |
| 438 | 找所有字母异位词 | Medium | 定长滑动窗口 + 计数 | 35 min |
| 239 | 滑动窗口最大值 | Hard | 单调递减队列 | 40 min |
| 76 | 最小覆盖子串 | Hard | 滑动窗口 + 需求计数 | 45 min |
六、易错点与技巧
- 滑动窗口 vs 双指针：滑动窗口解决”连续子区间”问题，双指针解决”两个元素的关系”问题
- 滑动窗口的边界：
right - left是窗口长度（右开区间），right - left + 1是闭区间长度 - 去重技巧：三数之和中的去重用
while跳过相邻重复值 - 接雨水的核心：当前位置能接的水 =
min(左边最高, 右边最高) - 当前高度 - 单调队列：滑动窗口最大值用双端队列
collections.deque，维护递减顺序
七、复杂度总结
| 模式 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 对撞指针 | O(n) | O(1) |
| 快慢指针 | O(n) | O(1) |
| 滑动窗口 | O(n) | O(k)，k 为字符集大小 |
| 排序 + 双指针 | O(n log n) | O(1) 或 O(n) |
八、参考与延伸
- 01-哈希表（滑动窗口常用哈希表辅助）
- 04-链表（快慢指针在链表中应用更广）
- labuladong 滑动窗口框架：https://labuladong.online/algo/
- 代码随想录双指针专题：https://programmercarl.com/