适用读者：遇到"连续子数组/子串"就写双层循环的人。
前置：S03-B02（数组）。
实测环境：Python 3.12.3；实测日期 2026-11-05。
覆盖旧文：3、5、11、15、16、18、26、27、28、30、75、76（12 张卡，3,402 点）。
覆盖扩展：E-S03-016（滑动窗口不变式）。
补写：#11 盛最多水的容器（原卡空壳，E-S03-111）、#27 移除元素（E-S03-112）。
上一篇：S03-X01 · 题解索引（LeetCode 1–100 + 笔记卡）
下一篇：S03-J02 · 二分查找。
1. 一句话结论
双指针之所以能去掉一层循环，是因为"移动方向单调"——某个指针只会往前，不会回头。这保证了每个元素最多被访问常数次。
| 类型 | 不变式 | 典型 |
|---|---|---|
| 对撞双指针 | 左右指针从两端向中间收，区间逐步缩小 | 有序数组求和、盛水、回文 |
| 快慢双指针 | 快指针探路，慢指针写结果 | 原地删除、链表找中点/环 |
| 滑动窗口 | [l, r] 内始终满足某条件；r 只进，l 在破坏条件时进 |
最长/最短子串、定长子数组 |
2. 实测：暴力为什么不行
"无重复字符的最长子串"（#3），构造全不相同字符的最坏输入：
| n | 暴力 O(n²) | 滑窗 O(n) | 结果 |
|---|---|---|---|
| 2,000 | 997.2 ms | 1.38 ms | 2000 ✅ |
| 4,000 | 3,699.5 ms | 4.19 ms | 4000 ✅ |
| 8,000 | 16,520.7 ms | 7.69 ms | 8000 ✅ |
n 翻倍暴力约 ×3.7–4.5（符合 O(n²)）；滑窗约 ×2（线性）。n=8,000 时已经差 2,148 倍，n=10⁵ 时暴力要几十分钟。
为什么滑窗是线性的：r 只前进 n 次，l 总共也只前进 n 次 → 总操作 O(n)。两个指针都不回头，这是全部收益的来源。
3. 通用模板（先记骨架，再记变体）
int l = 0, best = 0;
for (int r = 0; r < n; r++) {
// ① 进窗口：把 a[r] 纳入统计
add(a[r]);
// ② 判条件：窗口不合法时收缩
while (!valid()) {
remove(a[l]);
l++;
}
// ③ 更新答案（此时窗口一定合法）
best = Math.max(best, r - l + 1);
}
三个变体：
| 变体 | 关键差异 |
|---|---|
| 最长窗口 | 收缩到合法后更新答案（上面的模板） |
| 最短窗口 | 收缩时更新答案（while (valid()) { best = min(...); remove(a[l++]); }） |
| 定长窗口 | 只 if 不 while（窗口大小固定，每步移一格） |
4. 代表题精讲
4.1 #11 盛最多水的容器（补写 E-S03-111）
题目：给定高度数组，选两条垂线，使 min(h[l],h[r]) * (r-l) 最大。
关键洞察：面积由短板决定。若移动长板，宽度减少而高度不可能增加 → 面积只会更小。所以每次只移动短板那一侧。
int maxArea(int[] h) {
int l = 0, r = h.length - 1, best = 0;
while (l < r) {
best = Math.max(best, Math.min(h[l], h[r]) * (r - l));
if (h[l] < h[r]) l++; else r--; // 只移动短板
}
return best;
}
| 复杂度 | 值 |
|---|---|
| 时间 | O(n)（每步至少移动一个指针） |
| 空间 | O(1) |
为什么正确（一句话证明）：任何"跳过短板"的组合都不会比当前以该短板为边界的最优更好——因为宽度更小、高度受同一短板限制。
4.2 #27 移除元素（补写 E-S03-112）
题目：原地删除所有等于 val 的元素，返回新长度（顺序可变）。
int removeElement(int[] a, int val) {
int w = 0;
for (int r = 0; r < a.length; r++)
if (a[r] != val) a[w++] = a[r];
return w;
}
要点：返回值是新长度，a[0..w) 是有效区，a[w..) 的残留内容无意义（不要断言它被清零）。
4.3 #3 无重复最长子串
int lengthOfLongestSubstring(String s) {
int[] last = new int[128]; Arrays.fill(last, -1);
int l = 0, best = 0;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
if (last[c] >= l) l = last[c] + 1; // 直接跳到重复字符之后
last[c] = r;
best = Math.max(best, r - l + 1);
}
return best;
}
与通用模板的差异：这里不用 while，因为 last[c] 直接给出"应该跳到哪里"，避免了一次次收缩。
4.4 #76 最小覆盖子串（最短窗口变体）
窗口内维护 欠账 = 需要但还没凑齐的字符种类数：
while (欠账 == 0) { // 窗口已覆盖
best = min(best, r - l + 1); // 先更新（最短窗口）
if (--cnt[s.charAt(l)] < need(s.charAt(l))) 欠账++;
l++;
}
注意：最短窗口的答案更新在收缩循环内部，与最长窗口相反。
5. 12 题模式对照
| 题 | 类型 | 一句话 |
|---|---|---|
| 3 | 滑窗 + 哈希 | 记录字符最后位置，左指针跳跃 |
| 5 | 中心扩展 | 奇偶两种中心，向两侧扩 |
| 11 | 对撞 | 移动短板（补写） |
| 15 | 对撞 + 排序 | 固定一个数，去重靠"跳过相同值" |
| 16 | 对撞 + 排序 | 维护最接近差值 |
| 18 | 对撞 + 排序 | 两层固定 + 去重 |
| 26 | 读写指针 | 覆盖式去重 |
| 27 | 读写指针 | 覆盖式删除（补写） |
| 28 | KMP | 前缀函数，O(n+m) |
| 30 | 分组滑窗 | 按单词长分组 |
| 75 | 三路划分 | 一次遍历分三段 |
| 76 | 最短滑窗 | 欠账计数 |
6. 五个误区
| 误区 | 真相 |
|---|---|
| "滑窗能解决所有子串问题" | 要求"窗口扩大/收缩时条件单调"，否则要换方法 |
| "左指针也要遍历所有位置" | 左指针总共只移动 n 次（不回头） |
| "最长和最短窗口模板一样" | 更新答案的位置相反（收缩外 vs 收缩内） |
| "#27 返回后可以读尾部元素" | 尾部内容未定义 |
"去重靠 Set 就够" |
排序 + 跳过重复更省内存，且能保证字典序 |
7. 自检
- 滑窗为什么是 O(n)？用"两指针都不回头"解释。
- 最长窗口与最短窗口的答案更新位置为什么相反？
- #11 为什么只移动短板？
- #27 的返回值语义是什么？尾部元素能读吗？
- 什么情况下滑窗会失效？
8. 下一篇
S03-J02 · 二分查找：边界、旋转与答案二分
下一篇处理"另一个总写错的模板"：二分的循环不变量、mid 取整方向、以及四种常见死循环/漏解的复现。
本篇属于系列《S03 · 数据结构与算法》。旧文来源：12 张题解卡；补写 #11（E-S03-111）、#27（E-S03-112）。实测：n=8,000 暴力 16,520.7 ms vs 滑窗 7.69 ms。