算法设计范式
滑动窗口
滑动窗口是一种处理「连续一段元素」问题的技巧——比如子数组或子串——你在数据的一部分上维护一个「窗口」，并让它沿着滑动，而不是每次都从头把所有东西重看一遍。想象一个窗框搁在一排数字上：窗框向右移一步，右侧就有一个新元素进来、（通常）左侧有一个旧元素离开。要点在于，你只根据「进来了什么、离开了什么」来更新当前答案，绝不重新扫描整个窗口。
这种增量式更新就是它全部的胜处。暴力做法——比如要求「任意 k 个连续元素的最大和」——会把每个窗口的和从头重算，做 O(n·k)、也就是 O(n^2) 的工作。滑动窗口则只把第一个窗口的和算一次，之后每滑一步就加上进来的元素、减去出去的元素：每一步都是 O(1)，于是整趟扫描是 O(n)。同样的答案，工作量却大幅减少，且只需 O(1) 的额外空间。
窗口分两种口味。定长窗口保持宽度 k 不变，是最简单的情形（上面的滑动求和就是）。变长窗口会伸缩：你把右边界往外推以纳入更多，每当窗口违反条件时就把左边界往里收——这是「最长无重复字符子串」或「和至少为 S 的最短子数组」这类问题的标准套路。功夫在于精确地判断何时该收缩。滑动窗口只适用于连续的片段；若问题里顺序无所谓、或元素可以跳着选，它就不是对的工具。
int maxSum(const vector<int>& a, int k) {
int sum = 0;
for (int i = 0; i < k; ++i) sum += a[i]; // first window
int best = sum;
for (int i = k; i < a.size(); ++i) {
sum += a[i] - a[i - k]; // slide: add new, drop old
best = max(best, sum);
}
return best; // O(n) time, O(1) space
}加上进来的、减去出去的——O(n)，而非 O(n·k)。
滑动窗口其实是一种特化的双指针套路：左指针和右指针框住窗口，两者之间的元素就是窗口的内容。它要求「一个窗口的答案能从上一个窗口便宜地更新出来」——正是这种增量更新使它达到 O(n)。
又称
另见