第 7 章双指针与滑动窗口：不回头，就快了一个数量级

双指针有两种，长得不一样

同向双指针（滑动窗口）：两个指针都从左往右走，中间夹着的那一段就是「窗口」。用来对付「最长/最短的连续一段，满足某个条件」。
对撞双指针：一个从最左、一个从最右，面对面往中间走。用来对付「有序数组里找一对数」。

它们的共同点，也是这一章唯一的思想： 利用某种单调性，让指针只朝一个方向走，绝不回头。

上一章的前缀和是「提前把重复的活干完」，这一章是「顺着往前挪，边挪边改」—— 都是在对付同一个敌人：重复计算。

前半场 · 滑动窗口

1一句话问题

给 n 个正整数和一个上限 S，求「和不超过 S 的连续子段」最长有多长。

输入

10 12
4 2 1 7 8 1 2 8 1 5

输出

第一行是 n = 10 个数、目标 S = 12，第二行是那 n 个数。

⚠ 别急着往下读

先自己在纸上找一遍那段长度为 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暴力

brute.cpp暴力

// 最长的「和不超过 S」的连续子段 —— 暴力：枚举左端点，往右一直加
//
// 输入：第一行 n S
//       第二行 n 个正整数 a[1..n]
// 输出：一个整数，和不超过 S 的最长连续子段的长度（一个都放不下就输出 0）
//
// 「连续子段」= 数组里挨在一起的一小段，比如 a[3], a[4], a[5]。
// 注意是连续的 —— 不能挑着选，那是另一类题（背包，第 23 章）。
//
// 暴力思路：左端点 l 从 1 试到 n；固定 l 之后，右端点 r 一格一格往右挪，
// 边挪边累加，一旦超过 S 就停下来（后面只会更大，不用再试了）。
//
// 复杂度 O(n²)：最坏情况下每个 l 都要往右走很远。
// 那个 break 让它在 S 很小的时候跑得挺快，但只要 S 一大，它立刻原形毕露。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long S;
    if (!(cin >> n >> S)) return 0;

    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    int ans = 0;
    for (int l = 1; l <= n; l++) {
        long long sum = 0;
        for (int r = l; r <= n; r++) {
            sum += a[r];
            if (sum > S) break;              // 再往右只会更大
            ans = max(ans, r - l + 1);
        }
    }

    cout << ans << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

4实测：它有多慢

同题对比：每次退回去重走 vs 滑动窗口

数组长度 n

数据里每个数是 1~10，上限 S = 3n，所以最优窗口大约有半个数组那么长 —— 暴力那个 break 救不了它。跑完改成 200000 再来一次。

每次退回去重走

滑动窗口

本机实测：

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. 此刻窗口一定合法，更新答案
}

「进来一个 → 吐到合法 → 记录答案」，三步，顺序不能乱。

⚠ 那个 while 循环看起来像 O(n)，为什么总复杂度还是 O(n)？

初学者最常见的疑惑：外面一个 for，里面一个 while，这不是 O(n²) 吗？

不是。判断嵌套循环的复杂度不能只数层数，要数「总共执行了多少次」：

l 这个变量从 1 开始，只增不减，最多加到 n。所以那个 while 循环体在整个程序里一共只会执行 n 次，不是「每次外层循环都执行 n 次」。

均摊下来，每次外层循环平均只吐出 1 个数。 总共 O(n)。

这种「看着像平方、其实是线性」的分析方法叫均摊分析，在双指针、单调栈（第 35 章）里到处都是。学会数「总次数」而不是「层数」。

★ 滑动窗口的前提：单调性

这套做法能成立，靠的是一句话：窗口变长，和一定变大；窗口变短，和一定变小。

而这句话成立的前提是 数组里全是正数（非负也行）。

一旦有负数，往右伸可能让和变小，往左缩可能让和变大 —— 单调性没了，「右端点不回头」就不再正确，滑动窗口直接失效。

拿到一道题先问：这里有单调性吗？ 没有就别硬套。（有负数的区间和问题，通常要用前缀和 + 别的技巧，那是另一个故事。）

7正解

fast.cpp正解

// 最长的「和不超过 S」的连续子段 —— 滑动窗口（同向双指针）
//
// 输入输出和 brute.cpp 完全一样，但只扫一遍数组。
//
// 核心的观察（正文第 6 步会详细讲）：
//   暴力每次换左端点，都要把右端点**退回来重走一遍**。可仔细想想：
//   左端点往右挪一格，窗口里的和只会**变小**，那右端点根本没必要退回去 ——
//   它只需要接着往右走就行了。
//
//   于是两个指针都只往右走，各走 n 步，总共 O(n)。
//
// 写法上有个固定套路，记住这个形状：
//     for (r = 1..n) {
//         把 a[r] 加进窗口;
//         while (窗口不合法) { 把 a[l] 移出窗口; l++; }
//         用当前窗口更新答案;
//     }
//
// ⚠ 前提：数组里全是**正数**（或至少非负）。
//   有了它，「窗口变长和一定变大、窗口变短和一定变小」才成立，
//   l 才可以放心地永不回退。有负数的话这个单调性就没了，滑动窗口直接失效。
//   这是滑动窗口最重要的适用条件，比代码本身重要。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long S;
    if (!(cin >> n >> S)) return 0;

    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    int ans = 0;
    long long sum = 0;
    int l = 1;                                  // 窗口是 [l, r]

    for (int r = 1; r <= n; r++) {
        sum += a[r];                            // 右边进来一个

        while (l <= r && sum > S) {             // 超了就从左边吐出去，直到重新合法
            sum -= a[l];
            l++;
        }

        ans = max(ans, r - l + 1);              // 此刻的窗口一定是合法的
    }

    cout << ans << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

trace.cpp过程演示

跑完看最后一行：数一数 l 一共走了几步。它一次都没往回走过 —— 这就是 O(n) 的全部理由。

// 滑动窗口 —— 把两个指针的每一步都打印出来
//
// 输入：n S / n 个正整数（用小数据，n <= 20）
// 输出：每一步窗口的样子、当前和、以及指针是怎么动的
//
// 跑一遍，然后数两件事：
//   1. r 一共往右走了几步？ n 步。
//   2. l 一共往右走了几步？ 最多 n 步 —— 而且**它一次都没往回走过**。
//
// 两个指针各走不超过 n 步，加起来最多 2n 步，所以是 O(n)。
// 这个「各自单调前进」的计数方式，是双指针类算法复杂度分析的通用套路。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long S;
    if (!(cin >> n >> S)) return 0;
    if (n <= 0 || n > 20) { cout << "这份是用来看过程的，请用 1 <= n <= 20\n"; return 0; }

    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    cout << "数组：";
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << "　　上限 S = " << S << "\n\n";

    int ans = 0, l = 1, lMoves = 0;
    long long sum = 0;

    for (int r = 1; r <= n; r++) {
        sum += a[r];
        cout << "r 右移到 " << r << "：把 a[" << r << "] = " << a[r] << " 加进窗口，和 = " << sum << "\n";

        while (l <= r && sum > S) {
            cout << "    和 " << sum << " > " << S << " 超了 → 从左边吐出 a[" << l << "] = " << a[l];
            sum -= a[l];
            l++;
            lMoves++;
            cout << "，和 = " << sum << "，l 右移到 " << l << "\n";
        }

        int len = r - l + 1;
        cout << "    当前窗口 [" << l << ", " << r << "]  内容 ";
        for (int i = l; i <= r; i++) cout << a[i] << " ";
        cout << " 和 = " << sum << "  长度 " << len;
        if (len > ans) { ans = len; cout << "  ← 刷新了最长记录"; }
        cout << "\n";
    }

    cout << "\n答案：" << ans << "\n";
    cout << "r 一共走了 " << n << " 步，l 一共走了 " << lMoves << " 步 —— 两个指针都只往右，一次都没回头。\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

8单步看窗口滑动

滑动窗口：左指针永不回头

数组上限 S

第 1 / 30 步

窗口里的和

上限 S

当前窗口长度

最长记录

蓝色 = 当前窗口，浅绿 = 目前最长的那个窗口。格子下面的 l / r 就是两个指针。

目标：找一段连续的数，和不超过 S = 12，而且要尽量长。窗口一开始是空的。

「滑动窗口」这一栏，盯住 l 这个指针：

它只会往右，一次都不回头。
每次 r 前进一格，l 可能不动，也可能连续跳好几格 —— 但总步数加起来不超过 n。
浅绿色是目前最长的窗口。看着它一点点变长。

把上限 S 改成 0 试试：窗口永远是空的，答案 0。再改成 100（比总和还大）：窗口一直伸到底，答案就是 n。这两个边界待会儿对拍要用。

9★ 对拍验证

★ 正确的用法

把「滑动窗口」那一栏换成你自己默写的，再点开始。

对拍器

轮数

生成器专门造三种 S：0（一个数都放不下，答案 0）、刚好等于总和（答案 n）、中间随机。另外还会往数组里塞大数，制造「某个 a[i] 自己就超过 S」的情况 —— 那时窗口会变空，写不好就会算出负长度。

// 最长的「和不超过 S」的连续子段 —— 滑动窗口（同向双指针）
//
// 输入输出和 brute.cpp 完全一样，但只扫一遍数组。
//
// 核心的观察（正文第 6 步会详细讲）：
//   暴力每次换左端点，都要把右端点**退回来重走一遍**。可仔细想想：
//   左端点往右挪一格，窗口里的和只会**变小**，那右端点根本没必要退回去 ——
//   它只需要接着往右走就行了。
//
//   于是两个指针都只往右走，各走 n 步，总共 O(n)。
//
// 写法上有个固定套路，记住这个形状：
//     for (r = 1..n) {
//         把 a[r] 加进窗口;
//         while (窗口不合法) { 把 a[l] 移出窗口; l++; }
//         用当前窗口更新答案;
//     }
//
// ⚠ 前提：数组里全是**正数**（或至少非负）。
//   有了它，「窗口变长和一定变大、窗口变短和一定变小」才成立，
//   l 才可以放心地永不回退。有负数的话这个单调性就没了，滑动窗口直接失效。
//   这是滑动窗口最重要的适用条件，比代码本身重要。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long S;
    if (!(cin >> n >> S)) return 0;

    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    int ans = 0;
    long long sum = 0;
    int l = 1;                                  // 窗口是 [l, r]

    for (int r = 1; r <= n; r++) {
        sum += a[r];                            // 右边进来一个

        while (l <= r && sum > S) {             // 超了就从左边吐出去，直到重新合法
            sum -= a[l];
            l++;
        }

        ans = max(ans, r - l + 1);              // 此刻的窗口一定是合法的
    }

    cout << ans << "\n";
    return 0;
}

点一下即可编辑

值得故意写错的：

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

输出

第一行是 n = 8 个数、目标和 S = 12，第二行是那 n 个数（已排好序）。

三对是 (1, 11)、(3, 9)、(4, 8)。

暴力两重循环，O(n²)：

pairBrute.cpp暴力

// 和为 S 的数对 —— 暴力：两重循环试遍所有配对
//
// 输入：第一行 n S
//       第二行 n 个**互不相同**且**从小到大**排好序的整数
// 输出：满足 i < j 且 a[i] + a[j] == S 的数对个数
//
// 两重循环，O(n²)。n = 5 万就已经是 12.5 亿次比较了。
//
// （为什么要求互不相同？因为有重复元素时，对撞指针要成块处理，
//   代码会长出一截。正文里会把那段代码也给你，但主线先保持干净。）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long S;
    if (!(cin >> n >> S)) return 0;

    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long cnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (a[i] + a[j] == S) cnt++;

    cout << cnt << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

同题对比：两重循环 vs 对撞指针

数组长度 n

数据是 0, 2, 4, … 这样的升序序列，S 取首尾之和，中间有一大堆配对。

两重循环

对撞指针

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 章的剪枝是同一种智慧。

pairFast.cpp正解

// 和为 S 的数对 —— 对撞双指针
//
// 输入输出和 pairBrute.cpp 完全一样，但只扫一遍。
//
// 两个指针一个在最左、一个在最右，面对面往中间走：
//
//     和 < S  →  想让和变大，只能把左指针右移（数组是升序的，右移就变大）
//     和 > S  →  想让和变小，只能把右指针左移
//     和 = S  →  记一笔，两个指针同时往里收一格
//
// 为什么这样不会漏掉答案？关键是每一步「排除」的东西都是**确定没用**的：
//   当 a[l] + a[r] < S 时，a[l] 和右边任何一个数配对都 ≤ a[l] + a[r] < S，
//   所以 a[l] 这个数**跟谁都凑不出 S**，可以永久扔掉，l 放心右移。
//   （另一边同理。）
//
// 每一步至少扔掉一个数，所以最多 n 步，O(n)。
//
// ⚠ 前提：数组必须**有序**。无序的话「右移就变大」这个前提不成立，整套逻辑垮掉。
//   拿到一道题先想想「排序之后会不会有单调性」—— 这是双指针题的第一个念头。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long S;
    if (!(cin >> n >> S)) return 0;

    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long cnt = 0;
    int l = 1, r = n;

    while (l < r) {
        long long sum = a[l] + a[r];
        if (sum < S) l++;
        else if (sum > S) r--;
        else { cnt++; l++; r--; }
    }

    cout << cnt << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

回到上面的动画，切到「对撞指针（相向）」那一栏：

灰色的格子是已经被永久排除的数。它们不是「暂时跳过」，是再也不用看了。
每一步 caption 都会告诉你「为什么可以扔掉它」。看三遍，把那个理由说给自己听。

12★ 一个必须亲手撞一次的坑：重复元素

上面那份四行代码有个前提：元素互不相同。

⚠ 现在去动画里把数组改成 1 1 2 2、S 改成 3

它会数出 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 对。

pairDup.cpp能处理重复元素

★ 这一步真正要教的不是那段代码

是这个：你怎么才能发现自己漏了重复元素这种情况？

靠灵光一闪是不行的。靠的是让生成器去撞：把取值范围压窄（只有 0~5 六种值），重复必然大量出现。

下面这个对拍器就是这么造数据的。先用它跑「四行版」—— 它会在头几轮之内就被抓住（实测大约 43% 的数据能抓到它）。然后换成上面那份，才能全过。

对拍器

轮数

⚠ 这个对拍器是故意让你看它失败的：生成器只用 0~5 六种值，重复元素满地都是。先直接点「开始对拍」看四行版怎么翻车，再把它换成 pairDup.cpp 那份（或者你自己写的），看它全过。

// 和为 S 的数对 —— 对撞双指针
//
// 输入输出和 pairBrute.cpp 完全一样，但只扫一遍。
//
// 两个指针一个在最左、一个在最右，面对面往中间走：
//
//     和 < S  →  想让和变大，只能把左指针右移（数组是升序的，右移就变大）
//     和 > S  →  想让和变小，只能把右指针左移
//     和 = S  →  记一笔，两个指针同时往里收一格
//
// 为什么这样不会漏掉答案？关键是每一步「排除」的东西都是**确定没用**的：
//   当 a[l] + a[r] < S 时，a[l] 和右边任何一个数配对都 ≤ a[l] + a[r] < S，
//   所以 a[l] 这个数**跟谁都凑不出 S**，可以永久扔掉，l 放心右移。
//   （另一边同理。）
//
// 每一步至少扔掉一个数，所以最多 n 步，O(n)。
//
// ⚠ 前提：数组必须**有序**。无序的话「右移就变大」这个前提不成立，整套逻辑垮掉。
//   拿到一道题先想想「排序之后会不会有单调性」—— 这是双指针题的第一个念头。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long S;
    if (!(cin >> n >> S)) return 0;

    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long cnt = 0;
    int l = 1, r = n;

    while (l < r) {
        long long sum = a[l] + a[r];
        if (sum < S) l++;
        else if (sum > S) r--;
        else { cnt++; l++; r--; }
    }

    cout << cnt << "\n";
    return 0;
}

点一下即可编辑

13元素互不相同时的常规对拍

对拍器

轮数

这个生成器造的是互不相同的元素，四行版在这里是完全正确的。注意它有一半的概率把 S 取成「数组里真实存在的某两个数之和」—— 纯随机取 S 的话大多数轮次答案都是 0，那对拍就啥也验不出来。

// 和为 S 的数对 —— 对撞双指针
//
// 输入输出和 pairBrute.cpp 完全一样，但只扫一遍。
//
// 两个指针一个在最左、一个在最右，面对面往中间走：
//
//     和 < S  →  想让和变大，只能把左指针右移（数组是升序的，右移就变大）
//     和 > S  →  想让和变小，只能把右指针左移
//     和 = S  →  记一笔，两个指针同时往里收一格
//
// 为什么这样不会漏掉答案？关键是每一步「排除」的东西都是**确定没用**的：
//   当 a[l] + a[r] < S 时，a[l] 和右边任何一个数配对都 ≤ a[l] + a[r] < S，
//   所以 a[l] 这个数**跟谁都凑不出 S**，可以永久扔掉，l 放心右移。
//   （另一边同理。）
//
// 每一步至少扔掉一个数，所以最多 n 步，O(n)。
//
// ⚠ 前提：数组必须**有序**。无序的话「右移就变大」这个前提不成立，整套逻辑垮掉。
//   拿到一道题先想想「排序之后会不会有单调性」—— 这是双指针题的第一个念头。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long S;
    if (!(cin >> n >> S)) return 0;

    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long cnt = 0;
    int l = 1, r = n;

    while (l < r) {
        long long sum = a[l] + a[r];
        if (sum < S) l++;
        else if (sum > S) r--;
        else { cnt++; l++; r--; }
    }

    cout << cnt << "\n";
    return 0;
}

点一下即可编辑

14回头看：双指针的判断清单

★ 拿到一道题，问自己三句话

「答案是一段连续的区间」吗？ 是 → 考虑滑动窗口。
「排序之后，两端的选择有单调性」吗？ 是 → 考虑对撞指针。
那个单调性到底是什么？ 说不出来就别用 —— 双指针写错了往往还能过样例，然后在大数据上默默错掉。

顺便记住这两条前提，它们比代码重要：

	前提	一旦不满足
滑动窗口	数组非负（伸长和变大、缩短和变小）	有负数 → 单调性没了，直接失效
对撞指针	数组有序	无序 → 「右移就变大」不成立，逻辑垮掉

15自测

自测清单0 / 8

合上页面，白纸默写滑动窗口的那三步骨架把默写的贴进对拍器，300 轮通过说得出为什么「for 里套 while」总复杂度还是 O(n)（均摊分析）说得出滑动窗口为什么要求数组非负合上页面，白纸默写对撞指针的四行版说得出为什么 a[l] + a[r] < S 时可以永久扔掉 a[l]用重复元素的对拍器把四行版打假一次，再改对它完成下面至少 2 道练习题

配套练习

洛谷 P1147 连续自然数和解析 →　—— 滑动窗口模板题。连续自然数天然是正数，前提刚好满足
洛谷 P1102 A-B 数对解析 →　—— 排序 + 双指针（或二分）。注意重复元素 —— 这一章第 12 步刚踩过的坑
洛谷 P1638 逛画展解析 →　—— 滑动窗口 + 计数数组，求「包含全部种类的最短区间」。经典变形
洛谷 P1873 砍树解析 →　—— 这题其实是二分答案（下一章）。先自己想想能不能用双指针 —— 想清楚「为什么不能」，比会做还有价值

这一章我卡在哪（过一个月回来看，这几行比整章正文都值钱）

下一章预告

第 8 章二分查找。它和这一章是同一类思想的两个方向：双指针是「利用单调性，让指针不回头」，二分是「利用单调性，每次砍掉一半」。

而且二分有个出了名的坑 —— 边界写不对就死循环。下一章会把那个边界一次性钉死。