- 同向双指针（滑动窗口）：两个指针都从左往右走，中间夹着的那一段就是「窗口」。 用来对付「最长/最短的连续一段，满足某个条件」。
- 对撞双指针：一个从最左、一个从最右，面对面往中间走。 用来对付「有序数组里找一对数」。
它们的共同点，也是这一章唯一的思想： 利用某种单调性，让指针只朝一个方向走，绝不回头。
上一章的前缀和是「提前把重复的活干完」，这一章是「顺着往前挪，边挪边改」—— 都是在对付同一个敌人：重复计算。
前半场 · 滑动窗口
1 一句话问题
给 n 个正整数和一个上限 S，求「和不超过 S 的连续子段」最长有多长。
输入 10 12
4 2 1 7 8 1 2 8 1 5
输出 4先自己在纸上找一遍那段长度为 4 的子段，找到了再往下走。
这一步不能省 —— 你手动找的过程，就是接下来要写的算法。 而且你多半会自然而然地用上「左端点往右挪一格，右端点接着往下走」这个动作， 那正是这一章的关键。
「连续子段」= 数组里挨在一起的一小段。不能挑着选 —— 挑着选是另一类题（背包，第 23 章）。
2 先用纸笔手算一遍
固定左端点，往右伸，超了就停。像这样：
l=1: 4 → 6 → 7 → 14 超了，停。最长到 a[3]，长度 3
l=2: 2 → 3 → 10 → 18 超了，停。长度 3
l=3: 1 → 8 → 16 超了。长度 2
l=4: 7 → 15 超了。长度 1
l=5: 8 → 9 → 11 → 19 超了，停。长度 3
l=6: 1 → 3 → 11 → 12 ✓ → 17 超了，停。长度 4 ← 最长，就是 a[6..9]
l=7: 2 → 10 → 11 → 16 超了。长度 3
...现在盯住 l=1 和 l=2 这两行：
l=1时右端点走到了 4（超了停下）l=2时右端点又从 2 开始重新走了一遍
右端点退回去了。这就是暴力的全部问题。
3 暴力
点「运行 ▶」看结果
4 实测：它有多慢
本机实测：
| n | 暴力 O(n²) | 滑动窗口 O(n) |
|---|---|---|
| 20 000 | 0.11 秒 | 0.003 秒 |
| 50 000 | 0.68 秒 | 0.003 秒 |
| 100 000 | 2.71 秒 | 0.004 秒 |
brute.cpp 里有个 break：和一超过 S 就不往下试了。
所以如果 S 很小（窗口只有两三格），暴力其实很快 —— 它根本走不远。
只有当 S 大到窗口能拉得很长时，O(n²) 才真的兑现。
这件事对造数据的人很重要：genBig.cpp 里特意把 S 设成 3n，
就是为了让窗口长到半个数组。如果随手把 S 设小，这个对比就白做了 ——
你会得到「暴力也很快」的错误结论。
造数据前先想清楚「暴力的痛点在哪」，比把 n 调大有用得多。
5 慢在哪：右端点白白退回去了
回到第 2 步那张手算表。l 从 1 变成 2 的时候发生了什么？
窗口的左边少了一个数，所以和只会变小，绝不会变大。
既然和变小了，那原来因为「超了」而停下的右端点， 现在只可能走得更远，绝不可能要求它往回缩。
可暴力偏偏把它退回到了 l 的位置，重新一格一格走。这就是那个 O(n²) 的来源。
6 ★ 关键的一步
左端点右移时，右端点不用退回去 —— 让它待在原地，接着往右走就行。
于是两个指针都只朝右走，各自最多走 n 步，加起来最多 2n 步，O(n)。
代码有个固定形状，把它背下来：
int l = 1; long long sum = 0;
for (int r = 1; r <= n; r++) {
sum += a[r]; // 1. 右边进来一个
while (l <= r && sum > S) { // 2. 不合法就从左边吐出去
sum -= a[l];
l++;
}
ans = max(ans, r - l + 1); // 3. 此刻窗口一定合法，更新答案
}「进来一个 → 吐到合法 → 记录答案」，三步，顺序不能乱。
初学者最常见的疑惑：外面一个 for，里面一个 while，这不是 O(n²) 吗？
不是。判断嵌套循环的复杂度不能只数层数，要数「总共执行了多少次」：
l 这个变量从 1 开始，只增不减，最多加到 n。
所以那个 while 循环体在整个程序里一共只会执行 n 次，
不是「每次外层循环都执行 n 次」。
均摊下来，每次外层循环平均只吐出 1 个数。 总共 O(n)。
这种「看着像平方、其实是线性」的分析方法叫均摊分析， 在双指针、单调栈（第 35 章）里到处都是。学会数「总次数」而不是「层数」。
这套做法能成立，靠的是一句话：窗口变长，和一定变大；窗口变短，和一定变小。
而这句话成立的前提是 数组里全是正数（非负也行）。
一旦有负数，往右伸可能让和变小，往左缩可能让和变大 —— 单调性没了， 「右端点不回头」就不再正确，滑动窗口直接失效。
拿到一道题先问：这里有单调性吗？ 没有就别硬套。 （有负数的区间和问题，通常要用前缀和 + 别的技巧，那是另一个故事。）
7 正解
点「运行 ▶」看结果
点「运行 ▶」看结果
8 单步看窗口滑动
「滑动窗口」这一栏，盯住 l 这个指针：
- 它只会往右，一次都不回头。
- 每次
r前进一格，l可能不动，也可能连续跳好几格 —— 但总步数加起来不超过 n。 - 浅绿色是目前最长的窗口。看着它一点点变长。
把上限 S 改成 0 试试：窗口永远是空的，答案 0。
再改成 100（比总和还大）：窗口一直伸到底，答案就是 n。这两个边界待会儿对拍要用。
9 ★ 对拍验证
把「滑动窗口」那一栏换成你自己默写的，再点开始。
值得故意写错的：
while的条件漏掉l <= r→ 遇到「单个数就超过 S」时l会冲过r，长度变负ans = max(ans, r - l)（少加 1）→ 长度全部差一- 先更新答案再收缩窗口 → 会把不合法的窗口也算进去
- 把
sum声明成int→ 数据大时溢出（生成器造不出来，但比赛数据造得出来）
后半场 · 对撞双指针
10 一句话问题
给一个升序排好的数组（先假设元素互不相同）和目标 S，
问有多少对 i < j 满足 a[i] + a[j] == S。
输入 8 12
1 3 4 6 8 9 11 15
输出 3 (1,11)、(3,9)、(4,8)暴力两重循环，O(n²)：
点「运行 ▶」看结果
11 ★ 关键的一步：每一步都扔掉一个「注定没用」的数
两个指针，一个在最左（最小的数），一个在最右（最大的数）。
如果 a[l] + a[r] < S：
a[l] 是当前最小的数，它配上当前最大的 a[r] 都还不够 ——
那它配上剩下任何一个数都更不够。a[l] 跟谁都凑不出 S，永久扔掉，l++。
如果 a[l] + a[r] > S： 同理，a[r] 太大了，谁都救不了它，r--。
如果正好等于 S： 记一笔，两个指针同时往里收。
每一步都至少排除掉一个数，所以最多 n 步，O(n)。
注意这里的推理方式：不是「试一试这个方向对不对」， 而是证明了被扔掉的那个数不可能出现在任何答案里。 这种「安全地排除一大片」的思路，和第 4 章的剪枝是同一种智慧。
点「运行 ▶」看结果
回到上面的动画，切到**「对撞指针（相向）」**那一栏：
- 灰色的格子是已经被永久排除的数。它们不是「暂时跳过」，是再也不用看了。
- 每一步 caption 都会告诉你「为什么可以扔掉它」。看三遍，把那个理由说给自己听。
12 ★ 一个必须亲手撞一次的坑：重复元素
上面那份四行代码有个前提：元素互不相同。
它会数出 2 对。但正确答案是 4 对 —— 两个 1 各自都能和两个 2 配对。
原因：碰到相等时它只把 l 和 r 各挪一格，
于是「第 1 个 1 配第 2 个 2」「第 2 个 1 配第 1 个 2」这两对被跳过了。
正确做法是成块地数：左边有 cl 个相同的值、右边有 cr 个相同的值，
这一批就贡献 cl × cr 对；如果左右其实是同一块（a[l] == a[r]），
那就是从 k 个相同的数里任选两个，贡献 k(k-1)/2 对。
是这个：你怎么才能发现自己漏了重复元素这种情况？
靠灵光一闪是不行的。靠的是让生成器去撞： 把取值范围压窄（只有 0~5 六种值），重复必然大量出现。
下面这个对拍器就是这么造数据的。先用它跑「四行版」—— 它会在头几轮之内就被抓住（实测大约 43% 的数据能抓到它）。 然后换成上面那份，才能全过。
13 元素互不相同时的常规对拍
14 回头看：双指针的判断清单
- 「答案是一段连续的区间」吗？ 是 → 考虑滑动窗口。
- 「排序之后，两端的选择有单调性」吗？ 是 → 考虑对撞指针。
- 那个单调性到底是什么？ 说不出来就别用 —— 双指针写错了往往还能过样例，然后在大数据上默默错掉。
顺便记住这两条前提，它们比代码重要：
| 前提 | 一旦不满足 | |
|---|---|---|
| 滑动窗口 | 数组非负（伸长和变大、缩短和变小） | 有负数 → 单调性没了，直接失效 |
| 对撞指针 | 数组有序 | 无序 → 「右移就变大」不成立，逻辑垮掉 |
15 自测
- 洛谷 P1147 连续自然数和 —— 滑动窗口模板题。连续自然数天然是正数，前提刚好满足
- 洛谷 P1102 A-B 数对 —— 排序 + 双指针（或二分）。注意重复元素 —— 这一章第 12 步刚踩过的坑
- 洛谷 P1638 逛画展 —— 滑动窗口 + 计数数组，求「包含全部种类的最短区间」。经典变形
- 洛谷 P1873 砍树 —— 这题其实是二分答案（下一章）。先自己想想能不能用双指针 —— 想清楚「为什么不能」，比会做还有价值
第 8 章二分查找。它和这一章是同一类思想的两个方向： 双指针是「利用单调性，让指针不回头」，二分是「利用单调性，每次砍掉一半」。
而且二分有个出了名的坑 —— 边界写不对就死循环。下一章会把那个边界一次性钉死。