专题：双指针与滑动窗口 —— 两个指针都只往一个方向走

本讲定位：基础算法系列第 07 讲。这一讲是”初赛为主、复赛为辅”，依据是本库两份逐题统计：

• 复赛：双指针在 CSP-J 复赛七年 28 题、CSP-S 复赛七年 30 题里一次都没有当过主考点，唯一一次作为次考点是 CSP-S 2021 T3 回文（P7915）（见 cspj-series/cspj-round2-analysis-2019-2025.md §2 与 csps-series/csps-round2-analysis-2019-2025.md §2 的主考点频次表）；
• 初赛：CSP-S 阅读程序七年出现 4 段（2019 第(1)(3)段、2023 第(3)段、2025 第(3)段），CSP-S 完善程序 2023 年还有一段，CSP-J 阅读程序另有 2 段（2020、2025）。

所以本讲的篇幅刻意不写成第 04、05 讲那种级别，重点放在三件在别处找不到的事上：①窗口合法性不单调时到底错多少（实测）；②同一道题双指针 / 二分 / 哈希表的常数差多少（实测，两种编译选项）；③什么时候双指针就够、什么时候必须换单调队列（实测出交叉点）。

⚠️ 本讲不重讲双指针的四种形态。usaco-series/01-two-pointers.md 已经把对撞、同向、归并、读写四种形态按 Bronze→Silver→Gold 讲透了，例题全是 USACO 真题。本讲只用第 5 节一张表点一句并指路过去，两讲的分界写在 basic-series/00-syllabus.md §2.5。

本讲实测

⚠️ 编译选项：本讲代码块由 tools/check-cpp-blocks.py 用 g++ -std=c++11（不开 -O2） 编译运行，标注”不开 -O2“的耗时即该环境实测；标注”开 -O2“的是另跑一遍 g++ -std=c++11 -O2 的结果。耗时结论一律两列并排——第 04 讲发现过同一条结论在两种选项下方向相反，本讲第 4.2 节的交叉点也确实随选项移动（$k\approx15$ vs $k\approx30$）。错误率类结论与编译选项无关。

另一条口径：错误率与计数类数字用固定种子的 xorshift 生成，可逐位复现；耗时类数字有运行间抖动，同一台机器上重跑两次约差 3%~6%（例如第 3.1 节的”逐个二分”两次实测是 15.81x 与 15.50x，“哈希表”是 57.75x 与 54.70x）。所以本讲的耗时倍数一律按区间引用，代码块下方贴的是其中一次的原始输出。

1. “for 里套 while”的内层总次数被 $n$ 卡死，不是 $n^2$。 尺取模板实测：$n=10^6$ 时内层 while 总共只跑 999905 次，是 $n$ 的 0.9999 倍、是 $n^2$ 的 $1.0\times10^{-6}$ 倍。最坏构造（全 1、$S=1$）也恰好是 $n-1$ 次。
2. ⚠️ 窗口合法性不单调时，双指针的错误率随规模一路涨到 44.67%（$n\le4$ / $n\le16$ / $n\le2000$ 三档：1.84% → 16.47% → 44.67%）。全正数据对照组是 0.00% 全档——这个错只有造带负数的数据才测得出来。
3. ⚠️⚠️ “只放一个负数”是本库第七例”大数据反而测不出”：错误率 1.33% → 4.18% → 0.00%。$n\le2000$ 时一个负数几乎影响不到最短窗口，大数据一次都没测出来，中间档才是最危险的。
4. 最小反例只要三个数：$S=1$、序列 1 -1 1，正确答案 1，双指针输出 0——左指针被前面两个负数卡住，一步都不肯动。

顺带纠一处：usaco-series/01-two-pointers.md §4.1 建议用 S=3、序列 5 -4 3 当反例，实测这个反例不成立（双指针和暴力都输出 1）。已在那一讲改成上面这个。

5. 有序数组两数之和，三种解法的常数差得比复杂度更多（$n=5\times10^5$、20 次查询）。最坏情况（目标无解，三法都要走满）：双指针约 0.03 s、逐个二分 15.5~15.8x、哈希表 54.7~57.8x（不开 O2）；开 O2 后分别是 8.5x 与 9.9x——哈希表的劣势从五十多倍缩到 10 倍，选项一换结论的量级就变了。
6. ⚠️ 但”一般情况”会把差距掩盖掉：目标有解时双指针和二分都提前 return，二分只慢 1.2~1.3x（开 O2 只 1.07x）。拿有解数据测出来的”二分也不慢”是个假结论。
7. ⚠️ 窗口里要最值时，“双指针 + 一个变量记最大值”必错：三档错误率 24.70% / 45.47% / 55.50%，单调队列同数据 0.00% 全档。原因一句话：左端移出窗口时，那个变量收不回来。
8. 但单调队列不是免费的：$k$ 小的时候它反而更慢。 $n=10^5$ 实测，$k=2$ 时 $O(nk)$ 暴力比单调队列快 5 倍（开 O2 快 10 倍），交叉点在不开 O2 的 $k\approx15$、开 O2 的 $k\approx30$；$k=1000$ 时单调队列才快 35~37x / 24.7x。这与第 05 讲”$n=4$ 时剪枝反而亏”是同一类现象。
9. ⚠️ 两种写错法的错误率一模一样，都是 49.04% / 85.29% / 99.75%——收缩条件写成 s >= S（收过头）和长度写成 r - l（差一）。不是巧合：这两种写法都恰好在”有解”时出错、在”无解”时碰对，所以错误率等于随机数据里”有解”的比例。
10. l <= r 那个守卫，在前提成立时一次都没救过场：全正且 $S\ge1$ 时，去掉守卫，左指针越过右指针的比例是 0.00% 全档（各两万组）。但一旦允许负数且 $S\le0$，比例立刻升到 25.90%~26.60%，且三档几乎完全一样、与 $n$ 无关。它防的不是算错，是越界读。

前置与适合对象

前置：

• basic-series/01-prefix-sum-difference.md —— 窗口和的 $O(1)$ 维护就是那一讲”预处理换查询”的最小版本；第 2 节讲”为什么负数会破掉单调性”要用到前缀和不再递增这件事。
• basic-series/02-binary-search.md —— 第 3 节要把双指针和二分放在同一道题上比；初赛 2023 那段是二分答案套双指针。