19 · 双指针与滑动窗口

在 n = 2×10⁵ 的数组里找两个数，使它们的和等于 x。双重循环 O(n²) = 4×10¹⁰ 次比较，TLE。

如果数组是有序的，事情立刻不一样：l 指最左、r 指最右，看 a[l] + a[r] 与 x 的大小关系。和太大，说明 a[r] 配谁都太大，r 左移；和太小，说明 a[l] 配谁都太小，l 右移。每一步都能确定地丢掉一整排候选，而不是只丢一个。

• 两端收缩（对撞指针）：l 从左往右、r 从右往左，两者相向而行，直到 l ≥ r。前提是数组有序。
• 同向双指针（滑动窗口）：l、r 都只往右走，中间夹着的 [l, r] 叫窗口。r 负责扩张，l 负责收缩。

int best = n + 1;                  // 当前最优长度，n+1 表示“还没有”
// 收缩：只要窗口还覆盖全部 m 种，就试着把 l 往右推
while (have == m) {
    // 此刻不变式成立：[l, r] 覆盖了全部 m 种
    if (r - l + 1 < best) best = r - l + 1;
    if (--cnt[a[l]] == 0) --have;   // 移出 a[l]，可能弄丢一种
    ++l;                            // 让不变式可能被打破
}
// 退出时 have < m：[l, r] 已经不合法，正好可以继续右移 r

int l = 1; long long sum = 0;
int ans = n + 1;                       // n+1 表示“还没有答案”
for (int r = 1; r <= n; ++r) {
    sum += a[r];                       // 扩张
    while (sum >= S && l <= r) {       // 合法就缩短
        ans = min(ans, r - l + 1);
        sum -= a[l];                   // 收缩
        ++l;
    }
}

先看两端收缩。问题：给一个升序数组 a[1..n] 和 x，判断是否存在 i ≠ j 使 a[i] + a[j] = x。

int l = 1, r = n;
bool ok = false;
while (l < r) {
    int s = a[l] + a[r];
    if (s == x) { ok = true; break; }
    else if (s < x) ++l;      // a[l] 配谁都太小，这一整排候选全部作废
    else            --r;      // a[r] 配谁都太大，这一整列候选全部作废
}

为什么不会漏解？设当前 a[l] + a[r] < x。对任意 j ≤ r，因为数组升序，a[l] + a[j] ≤ a[l] + a[r] < x，所以 a[l] 和任何右端点都凑不出 x——l 可以永久丢弃。反过来 a[l] + a[r] > x 时，a[r] 配任何左端点都太大，r 可以永久丢弃。每一次移动都丢掉一整排，总共丢 n 次就结束。

所以两端收缩的真正前提是单调性：丢掉的东西以后不可能再有用。数组没排序时这个论证不成立，必须先花 O(n log n) 排序。

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

const int MAXN = 200005;
int a[MAXN];

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

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

    sort(a + 1, a + n + 1);        // 有了单调性，指针才有意义

    long long ans = 0;             // 最多约 2×10¹⁰，int 装不下
    int lo = 1, hi = 1;            // 窗口 [lo, hi) 装的是所有等于 a[i]+c 的位置
    for (int i = 1; i <= n; ++i) {
        long long t = (long long)a[i] + c;
        while (lo <= n && a[lo] < t) ++lo;      // lo 停在第一个 ≥ t 的位置
        while (hi <= n && a[hi] <= t) ++hi;     // hi 停在第一个 > t 的位置
        ans += hi - lo;                         // 窗口长度 = 值为 t 的元素个数
    }
    cout << ans << "\n";
    return 0;
}

再看同向双指针。问题：给 n 个正整数和目标 S，求最短的连续段，使段内元素和 ≥ S。

int l = 1, ans = n + 1;          // ans = n+1 表示“不存在”
long long sum = 0;
for (int r = 1; r <= n; ++r) {
    sum += a[r];                  // 扩张：把 a[r] 纳入窗口
    while (sum >= S && l <= r) {  // 合法就试着去掉左端
        ans = min(ans, r - l + 1);
        sum -= a[l];
        ++l;
    }
}

为什么能这么缩：所有数都是正数，所以固定 r 时 sum 随 l 增大而减小，l 越小越容易满足 sum ≥ S。于是对每个 r 只存在一个“最小的可行 l”，而且 r 增大时这个 l 只增不减——这正是双指针要求的那条单调性。反过来，如果允许负数，sum 不再随 l 单调，l 一旦右移可能永远回不到合法状态，答案就漏了。

窗口里要维护的东西不一定只有和。更常见的是计数：cnt[v] 表示值 v 在窗口里出现了几次。进窗口 ++cnt[a[r]]，出窗口 --cnt[a[l]]。如果要判断“窗口是否包含全部 m 种”，再维护一个 have = 窗口里的种类数：cnt 从 0 变 1 时 have++，从 1 变 0 时 have--。这样判断只要 O(1)；每轮扫一遍 cnt 数组去数种类，会把 O(n) 退化成 O(nm)。

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

const int MAXN = 1000005;      // n ≤ 10⁶，多留几位
const int MAXM = 2005;         // 画家编号 ≤ m ≤ 2×10³，开 2005 让下标 2000 安全
int a[MAXN], cnt[MAXM];

int main() {
    ios::sync_with_stdio(false);   // 10⁶ 个整数，必须提速
    cin.tie(nullptr);

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

    int l = 1, have = 0;           // have：窗口里出现过的画家种数
    int bl = 1, br = n;            // 当前最优区间，初值取整个数组（题目保证有解）
    for (int r = 1; r <= n; ++r) {
        if (cnt[a[r]]++ == 0) ++have;      // 先判断再自增：这位画家第一次进窗口
        while (have == m) {                // 覆盖全部画家，开始缩短
            if (r - l + 1 < br - bl + 1) { bl = l; br = r; }   // 严格更短才更新 → 保证 x 最小
            if (--cnt[a[l]] == 0) --have;  // 先自减再判断：窗口里再没有这位画家的画
            ++l;                           // 左边界右移，窗口变短
        }
    }
    cout << bl << " " << br << "\n";
    return 0;
}