演算法設計範式
滑動視窗
滑動視窗是一種處理「連續一段元素」問題的技巧——比如子陣列或子字串——你在資料的一部分上維護一個「視窗」，並讓它沿著滑動，而不是每次都從頭把所有東西重看一遍。想像一個窗框擱在一排數字上：窗框向右移一步，右側就有一個新元素進來、（通常）左側有一個舊元素離開。要點在於，你只根據「進來了什麼、離開了什麼」來更新當前答案，絕不重新掃描整個視窗。
這種增量式更新就是它全部的勝處。暴力做法——比如要求「任意 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)。
又稱
另見