滑动窗口

滑动窗口是同向双指针的一种：右指针不断扩张纳入新元素，一旦窗口不满足条件就收缩左指针，全程维护一个合法区间。适合“最长 / 最短满足某条件的连续子数组”这类问题。

以“元素为正，求和不超过 $k$ 的最长连续子数组”为例：

int l = 0, sum = 0, ans = 0;
for (int r = 0; r < n; r++) {
    sum += a[r];                // 右指针扩张
    while (sum > k) {           // 超了就收缩左边
        sum -= a[l];
        l++;
    }
    ans = max(ans, r - l + 1);  // 当前窗口长度
}

左右指针都只从头走到尾、各移动至多 $n$ 次，所以是 $O(n)$。

坑：一是这道题要求元素为正，收缩才有意义——若有负数，加元素不一定让和变大，窗口的单调性被破坏，就不能用滑窗；二是别忘了在窗口合法时更新答案，位置放错会漏解；三是窗口长度是 r - l + 1，减一加一容易写错。