双指针与滑动窗口模板
双指针与滑动窗口是数组/字符串题里出现频率最高的两类技巧。它们本质都是「用两个指针维护一个扫描状态，把 O(n²) 的暴力降到 O(n)」。
- 双指针：两个指针在数组上移动，分同向（快慢）与反向（对撞）。
- 滑动窗口：双指针的特例——左右指针之间夹着的「连续区间」就是窗口，靠窗口内统计信息判断收缩。
更细致的滑动窗口四类变体见 数组与字符串分类题解，本文重点是双指针分类与窗口的定长/变长模板。
一、核心思想
暴力：枚举所有子区间 [i, j]，需要 O(n²) 甚至 O(n³)
优化：利用单调性，用两个指针跳过不可能成为答案的区间
条件：随着 left 增大，right 的可行解区间单调移动（不回头）
三个关键问题：
- 指针怎么移动？ 同向（一起向右）还是反向（相向而行）？
- 移动的依据？ 当前状态满足/不满足某个条件，决定收缩还是扩张。
- 答案在哪一刻记录？ 收缩前、收缩后还是扩张后？
二、同向双指针模板（快慢指针）
同向双指针：fast 负责探测，slow 负责维护有效区间的左端点。典型场景是原地去重与链表环检测。
模板：数组原地去重（LeetCode 26）
def remove_duplicates(nums):
slow = 0 # 有效区间的最后一个位置
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
模板：链表环检测（LeetCode 141）
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
复杂度：O(n) 时间，O(1) 空间。
适用场景：有序数组去重、移动零（LC 283）、链表环/环入口（LC 142）、删除链表倒数第 N 个节点（LC 19，快指针先走 N 步）。
三、反向双指针模板（对撞指针）
反向双指针：left 从最左，right 从最右，相向移动。要求问题对 left、right 两侧的移动方向有单调的收益判断。
模板：两数之和 II（有序数组，LeetCode 167）
def two_sum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1]
elif s < target:
left += 1 # 和太小，左指针右移增大
else:
right -= 1 # 和太大，右指针左移减小
return []
例题：盛最多水的容器（LeetCode 11）
核心观察：容器的容量 = min(height[left], height[right]) * (right - left)。短板决定上限，移动较长的一边不可能让容量变大，所以移动较短的一边。
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1, ans = 0;
while (left < right) {
int area = min(height[left], height[right]) * (right - left);
ans = max(ans, area);
if (height[left] < height[right]) left++;
else right--;
}
return ans;
}
复杂度：O(n) 时间，O(1) 空间。
适用场景：有序两数之和、三数之和（LC 15）、盛水容器（LC 11）、接雨水（LC 42，先算两侧最高再对撞）、回文串判断（LC 125）。
对撞指针使用前提
单调性：在某一侧移动指针时，结果的变化方向是确定的。例如盛水容器——移动短板一侧，容器高度才可能上升；移动长板一侧，宽度减小且高度不可能增加，收益必降。没有这种单调性就不要用对撞指针。
四、滑动窗口模板
滑动窗口解决「连续子数组/子串」问题，核心是窗口内维护一个统计信息（计数、和、最值等）。
定长窗口模板（LC 643 / 239）
def fixed_window(nums, k):
# 先凑出第一个窗口
window_sum = sum(nums[:k])
ans = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # 右进左出
ans = max(ans, window_sum)
return ans
定长窗口是 O(n) 滑动，不需要收缩逻辑；若窗口内要维护最值，则配单调队列（LC 239 滑动窗口最大值）。
// LeetCode 239：单调队列维护窗口最大值
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> q = new ArrayDeque<>(); // 存下标，队首最大
int[] ans = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) q.pollLast();
q.offerLast(i);
if (q.peekFirst() <= i - k) q.pollFirst(); // 出窗口
if (i >= k - 1) ans[i - k + 1] = nums[q.peekFirst()];
}
return ans;
}
变长窗口模板（LC 209 / 3）
def min_subarray_len(nums, target):
# 最小可变窗口：找满足和 >= target 的最短子数组（LC 209）
left = window_sum = 0
ans = float('inf')
for right in range(len(nums)):
window_sum += nums[right] # 1. 扩大窗口
while window_sum >= target: # 2. 收缩窗口直到不满足
ans = min(ans, right - left + 1)
window_sum -= nums[left]
left += 1
return 0 if ans == float('inf') else ans
模板三步走（以「无重复字符的最长子串」LC 3 为例）：
def length_of_longest_substring(s):
seen = set()
left = ans = 0
for right in range(len(s)):
while s[right] in seen: # 收缩：窗口内有重复就左移
seen.remove(s[left])
left += 1
seen.add(s[right]) # 扩大：加入右端
ans = max(ans, right - left + 1) # 更新：此时窗口合法
return ans
变长窗口 - 最小覆盖子串（LC 76，模板完整版）
维护 need 与 valid，当 valid == len(need) 时窗口已覆盖全部目标字符，尝试收缩找最短。
from collections import Counter
def min_window(s, t):
need = Counter(t)
window = {}
left = valid = 0
start, length = 0, float('inf')
for right in range(len(s)):
c = s[right]
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
while valid == len(need): # 窗口已覆盖，尝试收缩
if right - left + 1 < length:
start, length = left, right - left + 1
d = s[left]
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
left += 1
return "" if length == float('inf') else s[start:start + length]
复杂度：均为 O(n) 时间（每个元素至多进出窗口一次），O(字符集) 空间。
五、前缀和 + 双指针/窗口结合
当窗口的「条件」是数值和，且元素可能为负数（此时 while 收缩不成立）时，改用前缀和 + 哈希表。
例题：和为 K 的子数组（LeetCode 560）
def subarray_sum(nums, k):
prefix = {0: 1} # 前缀和 -> 出现次数
cur = ans = 0
for num in nums:
cur += num
ans += prefix.get(cur - k, 0) # 存在以某个左边界结尾的和为 cur-k
prefix[cur] = prefix.get(cur, 0) + 1
return ans
与双指针的分工：
| 场景 | 推荐方法 | 原因 |
|---|---|---|
| 全为正数，求满足和的区间 | 滑动窗口（LC 209） | 窗口和随 right 单调增，可 while 收缩 |
| 存在负数，求满足和的区间 | 前缀和 + 哈希表（LC 560） | 和不再单调，窗口法失效 |
| 有序数组找两数 | 对撞指针（LC 167） | 利用有序单调性 |
| 无序数组找两数 | 哈希表（LC 1） | 一次遍历记录已见 |
六、经典题速查表
| 题号 | 题目 | 技巧 | 难度 |
|---|---|---|---|
| LeetCode 3 | 无重复字符的最长子串 | 变长窗口 | Medium |
| LeetCode 11 | 盛最多水的容器 | 对撞指针 | Medium |
| LeetCode 15 | 三数之和 | 排序 + 对撞 | Medium |
| LeetCode 76 | 最小覆盖子串 | 变长窗口 | Hard |
| LeetCode 209 | 长度最小的子数组 | 变长窗口 | Medium |
| LeetCode 239 | 滑动窗口最大值 | 定长窗口 + 单调队列 | Hard |
| LeetCode 141/142 | 环形链表 | 快慢指针 | Easy/Medium |
| LeetCode 167 | 两数之和 II | 对撞指针 | Medium |
| LeetCode 560 | 和为 K 的子数组 | 前缀和 + 哈希 | Medium |
| LeetCode 713 | 乘积小于 K 的子数组 | 变长窗口 | Medium |
七、面试常见问题
Q: 什么时候用滑动窗口，什么时候用对撞指针？
- 滑动窗口：要求连续子区间，且窗口内条件随扩大/收缩单调可判（多为非负数组）。
- 对撞指针：有序性 + 两端单调收益，典型如两数之和、盛水容器。
- 快慢指针：链表问题或原地数组操作（去重、移动零）。
Q: 收缩用 while 还是 if？
用 while。因为左指针可能要连续移动多步才能重新满足条件（如 LC 76 里要减去多个字符才让 valid 下降）。
Q: 窗口里统计什么？用什么数据结构？
- 字符计数：哈希表，或定长数组
[26]/[128]/[256]。 - 窗口最大值：单调队列。
- 窗口元素去重：
set（如 LC 3）。 - 窗口内中位数：两个堆或有序集合（LC 480）。
Q: 为什么双指针能把 O(n²) 降为 O(n)？
每个指针最多从头走到尾各一次（同向）或各移动 n 次（对撞），总移动次数 O(n)，配合单调性跳过了大量不可能区间。
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。