滑動視窗 — 固定與可變視窗模板完整解析 | 資料結構與演算法
2026/07/02
滑動視窗（Sliding Window） 是在線性序列上維護一個連續區間，透過右指標擴展、左指標收縮，將原本需要 O(n²) 暴力枚舉的子陣列/子字串問題降至 O(n) 的演算法技巧。它是 雙指標 的特化形式，核心在於「如何維護視窗狀態」與「何時收縮視窗」這兩個判斷。掌握固定視窗與可變視窗兩種模板，能讓你輕鬆應對 LeetCode 中大量子陣列與子字串類的面試高頻題。
前言
想像你坐在火車上看窗外風景。火車向前行駛時，視窗框住的景色不斷更新——新的景色從右邊進入，舊的景色從左邊離開。視窗本身的大小可以是固定的（列車車窗），也可以是可調整的（你手裡拿著的相框，隨時可以縮放）。
這就是**滑動視窗（Sliding Window）**的核心直覺：用左右兩個指標框出一個連續的「視窗」，隨著問題的需求動態調整這個視窗的位置與大小，同時維護視窗內的狀態（如總和、字元計數），避免從零開始重算。
讀完這篇文章，你將能夠：
- 理解滑動視窗如何將 O(n²) 暴力解降至 O(n)，以及背後的攤銷分析
- 掌握固定長度視窗與可變長度視窗兩種模板的寫法與使用時機
- 用 TypeScript 解出 LeetCode 209、3、76、438、567 五道高頻考題
- 看懂 C++ 對照版本，理解
unordered_map與頻率陣列的選擇邏輯 - 知道何時選滑動視窗、何時改用前綴和，以及兩者的本質差異
核心概念
滑動視窗 vs 暴力枚舉
以「長度為 k 的子陣列最大和」為例，暴力法對每個起點重新加總 k 個元素，共 O(nk) 次加法。但你會注意到，相鄰兩個視窗有 k-1 個元素重疊——把最左邊的元素移除、把最右邊的新元素加入，一次更新只需 O(1)。這就是固定視窗的核心優化。
陣列：[1, 3, -1, -3, 5, 3] k=3
暴力：[1+3-1], [3-1-3], [-1-3+5], [-3+5+3] → 4次加法 × 每次k個
滑動：初始 1+3+(-1)=3，之後每次 -arr[left] + arr[right] → 每次O(1)
固定視窗 vs 可變視窗
| 類型 | 視窗大小 | 右指標行為 | 左指標行為 | 適用場景 |
|---|---|---|---|---|
| 固定視窗 | 恆為 k | 每步前進一格 | 與右指標同步，差值保持 k | 固定長度子陣列的最大/最小/平均值 |
| 可變視窗 | 由條件決定 | 每步擴展一格 | 條件不滿足時收縮 | 最長/最短滿足條件的子陣列/子字串 |
何時擴展、何時收縮的判斷原則：
- 目標是「最長」→ 盡量擴展，僅在違規時收縮
- 目標是「最短」→ 合法就嘗試收縮，找最小合法視窗
為什麼時間複雜度是 O(n)？
可變視窗有兩層迴圈，看起來像 O(n²)。但左右指標各自都是單向前進、不回頭：右指標最多走 n 步，左指標最多走 n 步，合計最多 2n 次操作。這是攤銷分析（Amortized Analysis）的經典案例——單次收縮可能執行多步，但所有收縮的步數加起來不超過 n。
ASCII 視覺化：可變視窗的展開與收縮
以最長無重複子串 "abcba" 為例，逐步追蹤視窗狀態：
Step 1: right=0, 加入 'a'，視窗合法
[ a ] b c b a
L=0 R=0
window: {a:1}, len=1, ans=1
Step 2: right=1, 加入 'b'，視窗合法
[ a b ] c b a
L=0 R=1
window: {a:1, b:1}, len=2, ans=2
Step 3: right=2, 加入 'c'，視窗合法
[ a b c ] b a
L=0 R=2
window: {a:1, b:1, c:1}, len=3, ans=3
Step 4: right=3, 加入 'b'，發現重複！開始收縮
a [ b c b ] a ← 移除 'a'，left=1，'b' 仍重複
a b [ c b ] a ← 移除 'b'，left=2，視窗合法
L=2 R=3
window: {c:1, b:1}, len=2, ans=3（保持）
Step 5: right=4, 加入 'a'，視窗合法
a b [ c b a ]
L=2 R=4
window: {c:1, b:1, a:1}, len=3, ans=3
最終答案：3（"abc" 或 "cba"）
JS / TypeScript 實作
固定視窗模板
固定視窗的模板最為精簡：先初始化前 k 個元素建立第一個視窗，之後每次用「加入新元素 - 移除最左元素」更新視窗狀態。
/**
* 固定長度視窗模板：長度為 k 的子陣列最大和
* 對應 LeetCode 643 - Maximum Average Subarray I
* 時間：O(n) 空間：O(1)
*/
function maxSumSubarrayFixed(nums: number[], k: number): number {
if (nums.length < k) return -Infinity;
// 初始化第一個視窗 [0, k-1]
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += nums[i];
}
let maxSum = windowSum;
// 每次滑動：加入右側新元素，移除左側最舊元素
for (let right = k; right < nums.length; right++) {
windowSum += nums[right] - nums[right - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// 測試
console.log(maxSumSubarrayFixed([1, 12, -5, -6, 50, 3], 4)); // 51（[-6, 50, 3] 不對，應是 [12,-5,-6,50]=51）
console.log(maxSumSubarrayFixed([2, 3, 4, 1, 5], 2)); // 7（[3,4]）
可變視窗模板（搭配 HashMap）
可變視窗的核心是「擴展 → 檢查 → 收縮 → 更新答案」這個迴圈，答案必須在內層 while 之後更新（確保視窗處於合法狀態）。
/**
* 可變視窗通用模板：最多包含 k 個不同字元的最長子串
* 時間：O(n) 空間：O(k)
*/
function longestSubstringWithKDistinct(s: string, k: number): number {
const freq = new Map<string, number>();
let left = 0;
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
// Step 1：擴展 — 加入右側字元
const rightChar = s[right];
freq.set(rightChar, (freq.get(rightChar) ?? 0) + 1);
// Step 2：收縮 — 當不同字元種類超過 k，移除左側字元
while (freq.size > k) {
const leftChar = s[left];
const count = freq.get(leftChar)! - 1;
if (count === 0) {
freq.delete(leftChar); // 計數歸零務必刪除，否則 freq.size 會計算到空條目
} else {
freq.set(leftChar, count);
}
left++;
}
// Step 3：更新答案 — 此時視窗一定合法
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
實作一：最短子陣列使其和 ≥ S（LeetCode 209）
此題是可變視窗「找最短合法視窗」的典型代表：右指標擴展直到視窗和達標，然後嘗試收縮左邊界讓視窗更短。
/**
* Minimum Size Subarray Sum
* 找最短的連續子陣列，使其和 >= target
* 時間：O(n) 空間：O(1)
*/
function minSubArrayLen(target: number, nums: number[]): number {
let left = 0;
let windowSum = 0;
let minLen = Infinity;
for (let right = 0; right < nums.length; right++) {
windowSum += nums[right]; // 擴展：加入右側元素
// 當視窗和達標：嘗試持續收縮，找最小合法視窗
while (windowSum >= target) {
minLen = Math.min(minLen, right - left + 1);
windowSum -= nums[left]; // 移除最左元素
left++;
}
}
// 若從未達標，返回 0
return minLen === Infinity ? 0 : minLen;
}
// 測試
console.log(minSubArrayLen(7, [2, 3, 1, 2, 4, 3])); // 2（[4,3]）
console.log(minSubArrayLen(4, [1, 4, 4])); // 1（[4]）
console.log(minSubArrayLen(11, [1, 1, 1, 1, 1, 1])); // 0（無解）
實作二：最長無重複子串（LeetCode 3）
這是可變視窗最經典的入門題。進階技巧：用 Map 記錄字元最後出現的索引，讓 left 直接跳至重複位置的下一格，避免逐步收縮。
/**
* Longest Substring Without Repeating Characters
* 時間：O(n) 空間：O(min(n, charset))
*/
function lengthOfLongestSubstring(s: string): number {
// 記錄字元最後出現索引，比 Set 更高效（可直接跳躍 left）
const lastIndex = new Map<string, number>();
let left = 0;
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
// 若字元重複且在當前視窗內，直接跳躍 left（非逐步收縮）
if (lastIndex.has(char) && lastIndex.get(char)! >= left) {
left = lastIndex.get(char)! + 1;
}
lastIndex.set(char, right); // 更新最後出現索引
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// 測試
console.log(lengthOfLongestSubstring("abcabcbb")); // 3（"abc"）
console.log(lengthOfLongestSubstring("bbbbb")); // 1（"b"）
console.log(lengthOfLongestSubstring("pwwkew")); // 3（"wke"）
實作三：最小覆蓋子串（LeetCode 76）
這是滑動視窗的硬題代表。關鍵是用 have 計數器追蹤「已滿足需求的不同字元數」，避免每次比較整個 Map。
/**
* Minimum Window Substring
* 找出 s 中包含 t 所有字元的最短子串
* 時間：O(|s| + |t|) 空間：O(|s| + |t|)
*/
function minWindow(s: string, t: string): string {
if (s.length < t.length) return "";
// 建立目標字元頻率表
const need = new Map<string, number>();
for (const char of t) {
need.set(char, (need.get(char) ?? 0) + 1);
}
const window = new Map<string, number>();
let left = 0;
let have = 0; // 當前視窗中已滿足的不同字元數
const required = need.size; // 需要滿足的不同字元總數
let minLen = Infinity;
let minLeft = 0;
for (let right = 0; right < s.length; right++) {
// 擴展：加入右側字元
const char = s[right];
window.set(char, (window.get(char) ?? 0) + 1);
// 若該字元剛好達到需求數量，have++
if (need.has(char) && window.get(char) === need.get(char)) {
have++;
}
// 收縮：當所有字元均已滿足，嘗試縮小視窗
while (have === required) {
const windowLen = right - left + 1;
if (windowLen < minLen) {
minLen = windowLen;
minLeft = left;
}
// 移除左側字元
const leftChar = s[left];
window.set(leftChar, window.get(leftChar)! - 1);
if (need.has(leftChar) && window.get(leftChar)! < need.get(leftChar)!) {
have--;
}
left++;
}
}
return minLen === Infinity ? "" : s.substring(minLeft, minLeft + minLen);
}
// 測試
console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"
console.log(minWindow("a", "a")); // "a"
console.log(minWindow("a", "aa")); // ""
C++ 對照
固定視窗：最大子陣列和
#include <vector>
#include <algorithm>
#include <numeric>
/**
* 固定視窗：最大子陣列和
* 時間：O(n) 空間：O(1)
*/
int maxSumSubarray(const std::vector<int>& nums, int k) {
if (static_cast<int>(nums.size()) < k) return INT_MIN;
// 利用 STL accumulate 初始化第一個視窗
int windowSum = std::accumulate(nums.begin(), nums.begin() + k, 0);
int maxSum = windowSum;
for (int right = k; right < static_cast<int>(nums.size()); right++) {
windowSum += nums[right] - nums[right - k];
maxSum = std::max(maxSum, windowSum);
}
return maxSum;
}
最長無重複子串（C++）
#include <string>
#include <unordered_map>
#include <algorithm>
/**
* LeetCode 3 — C++ 版本
* 使用 unordered_map 記錄最後出現索引
* 時間：O(n) 空間：O(min(n, charset))
*/
int lengthOfLongestSubstring(const std::string& s) {
std::unordered_map<char, int> lastIndex;
int left = 0;
int maxLen = 0;
for (int right = 0; right < static_cast<int>(s.size()); right++) {
char c = s[right];
auto it = lastIndex.find(c);
// 若字元在當前視窗內出現過，直接跳躍 left
if (it != lastIndex.end() && it->second >= left) {
left = it->second + 1;
}
lastIndex[c] = right;
maxLen = std::max(maxLen, right - left + 1);
}
return maxLen;
}
最小覆蓋子串（C++）
#include <string>
#include <unordered_map>
#include <climits>
/**
* LeetCode 76 — C++ 版本
* 時間：O(|s| + |t|) 空間：O(|s| + |t|)
*/
std::string minWindow(const std::string& s, const std::string& t) {
if (s.size() < t.size()) return "";
std::unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, have = 0;
int required = static_cast<int>(need.size());
int minLen = INT_MAX, minLeft = 0;
for (int right = 0; right < static_cast<int>(s.size()); right++) {
char c = s[right];
window[c]++;
// 達到需求數量時，have++
if (need.count(c) && window[c] == need[c]) {
have++;
}
// 所有字元均已滿足：嘗試收縮
while (have == required) {
int windowLen = right - left + 1;
if (windowLen < minLen) {
minLen = windowLen;
minLeft = left;
}
char lc = s[left];
window[lc]--;
if (need.count(lc) && window[lc] < need[lc]) {
have--;
}
left++;
}
}
return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
}
複雜度分析總表
| 問題 | 視窗類型 | 時間複雜度 | 空間複雜度 | 狀態資料結構 |
|---|---|---|---|---|
| 固定長度子陣列最大和（643） | 固定 | O(n) | O(1) | 單一總和變數 |
| 最短子陣列使和 ≥ S（209） | 可變（找最短） | O(n) | O(1) | 單一總和變數 |
| 最長無重複子串（3） | 可變（找最長） | O(n) | O(min(n, charset)) | HashMap/Set |
| 最小覆蓋子串（76） | 可變（找最短） | O(|s|+|t|) | O(|s|+|t|) | 雙 HashMap |
| 字串排列包含（567） | 固定 | O(|s1|+|s2|) | O(26) | 頻率陣列 |
| 找到字串中所有異位詞（438） | 固定 | O(|s|+|p|) | O(26) | 頻率陣列 |
空間複雜度注意：「O(1)」指不使用額外的 HashMap，但 charset 為字元集大小（ASCII 為 128、小寫英文為 26），在面試中可依情況說明。
變體與延伸
字元頻率視窗：字串排列包含（LeetCode 567）
這題用固定視窗（大小等於 s1.length）加頻率陣列比較，是固定視窗的字串應用範本。matches 計數器追蹤「已滿足的字元種類數」，避免每次比較整個陣列。
/**
* Permutation in String
* 判斷 s2 中是否存在 s1 的排列（異位詞）
* 固定視窗（大小 = s1.length） + 頻率陣列比較
* 時間：O(|s1| + |s2|) 空間：O(26)
*/
function checkInclusion(s1: string, s2: string): boolean {
if (s1.length > s2.length) return false;
const need = new Array<number>(26).fill(0);
const have = new Array<number>(26).fill(0);
for (const c of s1) need[c.charCodeAt(0) - 97]++;
const A = 97; // 'a' 的 ASCII 碼
let matches = 0; // 已滿足的字元種類數
const totalNeeded = need.filter(n => n > 0).length;
for (let right = 0; right < s2.length; right++) {
// 加入右側字元
const ri = s2.charCodeAt(right) - A;
have[ri]++;
if (need[ri] > 0 && have[ri] === need[ri]) matches++;
// 固定視窗：移除最左元素（視窗大小超過 s1.length 時）
if (right >= s1.length) {
const li = s2.charCodeAt(right - s1.length) - A;
if (need[li] > 0 && have[li] === need[li]) matches--;
have[li]--;
}
if (matches === totalNeeded) return true;
}
return false;
}
// 測試
console.log(checkInclusion("ab", "eidbaooo")); // true（"ba" 是 "ab" 的排列）
console.log(checkInclusion("ab", "eidboaoo")); // false
多條件視窗：「恰好 k 個」的轉換技巧
有些問題要求「恰好包含 k 個不同字元的子陣列數量」。直接做難以收縮，但可以轉換為「最多 k 個」減去「最多 k-1 個」，化難為易。
/**
* 恰好包含 k 個不同整數的子陣列數量
* 轉換：f(恰好k) = f(最多k) - f(最多k-1)
* 時間：O(n) 空間：O(k)
*/
function subarraysWithKDistinct(nums: number[], k: number): number {
// 計算「最多 k 個不同整數」的子陣列數量
function atMostK(k: number): number {
const freq = new Map<number, number>();
let left = 0;
let count = 0;
for (let right = 0; right < nums.length; right++) {
freq.set(nums[right], (freq.get(nums[right]) ?? 0) + 1);
while (freq.size > k) {
const leftVal = nums[left];
const c = freq.get(leftVal)! - 1;
if (c === 0) freq.delete(leftVal);
else freq.set(leftVal, c);
left++;
}
// 以 right 為右端點的合法子陣列數 = right - left + 1
count += right - left + 1;
}
return count;
}
return atMostK(k) - atMostK(k - 1);
}
// 測試
console.log(subarraysWithKDistinct([1, 2, 1, 2, 3], 2)); // 7
console.log(subarraysWithKDistinct([1, 2, 1, 3, 4], 3)); // 3
面試考點
何時選擇滑動視窗
面試中判斷是否使用滑動視窗，可以問自己這幾個問題：
- 問題是否涉及連續子陣列/子字串？ 如果是不連續的子序列，滑動視窗無法使用。
- 是否在找最長、最短、或計算視窗內的某個值？ 這是滑動視窗的核心適用場景。
- 視窗的收縮條件是否清晰可定義？ 若難以定義「何時視窗不合法」，可能需要其他方法。
| 問題特徵 | 推薦方法 |
|---|---|
| 固定長度子陣列，求最大/最小 | 固定視窗滑動 |
| 最長/最短子陣列，滿足某條件 | 可變視窗滑動 |
| 子陣列的和等於某值（允許負數） | 前綴和 + HashMap |
| 子陣列的和等於某值（全正整數） | 可變視窗滑動 |
| 非連續子序列問題 | 動態規劃/雙指標（非滑動視窗） |
滑動視窗 vs 前綴和
兩者常被混淆，本質差異在於：
- 滑動視窗：適合全正整數（視窗可以明確定義「何時收縮」）；視窗大小動態調整；一次遍歷 O(n)。
- 前綴和：適合含負數的情況（無法用收縮條件定義視窗）；需要額外的 HashMap 記錄前綴和；O(n) 時間 O(n) 空間。
典型例子：LeetCode 560「和為 k 的子陣列數量」，因為陣列含負數，視窗不具單調性，無法使用滑動視窗，必須改用前綴和 + HashMap。
LeetCode 練習題單
| # | 題目 | 難度 | 視窗類型 | 核心技巧 |
|---|---|---|---|---|
| 209 | Minimum Size Subarray Sum | Medium | 可變（找最短） | 和達標後持續收縮 |
| 3 | Longest Substring Without Repeating Characters | Medium | 可變（找最長） | HashMap 記錄最後索引，直接跳躍 left |
| 76 | Minimum Window Substring | Hard | 可變（找最短） | 雙 HashMap + have/need 計數器 |
| 438 | Find All Anagrams in a String | Medium | 固定 | 頻率陣列 + matches 計數器 |
| 567 | Permutation in String | Medium | 固定 | 頻率陣列比較，與 438 同模板 |
建議練習順序：先做 209（可變視窗最清晰的起手式），再做 3（HashMap 應用），然後 567（固定視窗字串版），接著 438（567 的延伸），最後 76（最小覆蓋子串，硬題整合前面所有技巧）。
常見陷阱
陷阱一：答案更新時機錯誤
可變視窗中，答案必須在內層 while 之後更新，此時視窗才處於合法狀態。
// 錯誤：在收縮過程中更新答案，可能記錄到不合法視窗的長度
while (freq.size > k) {
maxLen = Math.max(maxLen, right - left + 1); // 此時視窗還不合法！
left++;
}
// 正確：收縮完成後再更新
while (freq.size > k) {
// ... 收縮邏輯
left++;
}
maxLen = Math.max(maxLen, right - left + 1); // 視窗已合法
陷阱二：字元計數歸零未從 Map 刪除
當字元計數降至 0 時，必須從 Map 中刪除，否則 freq.size 會計算到空計數的字元，導致收縮條件誤判。
// 錯誤：計數歸零未刪除
const count = freq.get(leftChar)! - 1;
freq.set(leftChar, count); // 若 count=0，freq.size 仍計算此字元！
// 正確：計數歸零時刪除條目
const count = freq.get(leftChar)! - 1;
if (count === 0) {
freq.delete(leftChar);
} else {
freq.set(leftChar, count);
}
陷阱三：固定視窗初始化邊界
固定視窗需先填充前 k 個元素建立初始視窗，再從 index = k 開始滑動。若直接從 0 開始滑動，第一次移除 nums[-k] 會越界或得到 undefined。
// 錯誤：沒有初始化視窗，從 right=0 開始滑動
for (let right = 0; right < nums.length; right++) {
windowSum += nums[right] - nums[right - k]; // right=0 時 nums[-k] = undefined！
}
// 正確：先建立初始視窗，再從 k 開始滑動
let windowSum = 0;
for (let i = 0; i < k; i++) windowSum += nums[i]; // 初始視窗
for (let right = k; right < nums.length; right++) {
windowSum += nums[right] - nums[right - k]; // 移除 nums[right-k]，加入 nums[right]
}
陷阱四：收縮條件用 if 而非 while
每次右指標擴展一格後，可能需要收縮多次才能讓視窗重新合法（例如一次加入導致多個字元超量）。必須用 while 持續收縮，而非用 if 只收縮一次。
// 錯誤：用 if，最多收縮一次
if (freq.size > k) {
// 只移除一個左側字元，視窗可能仍然不合法
}
// 正確：用 while，持續收縮直到合法
while (freq.size > k) {
// 持續移除左側字元，直到條件滿足
}
總結
滑動視窗（Sliding Window）是雙指標演算法家族中應用最廣的分支，用一個動態的「視窗」替代雙重迴圈的暴力枚舉，將子陣列/子字串問題的時間複雜度從 O(n²) 降至 O(n)。
這篇文章涵蓋了兩種核心模板：
- 固定視窗：視窗大小 k 恆定，每次滑動一格，用「加一個、減一個」更新狀態；適合求固定長度子陣列的最大/最小/平均值
- 可變視窗：由收縮條件決定視窗大小，右指標擴展、左指標依條件收縮；適合求最長/最短滿足條件的子陣列/子字串
掌握這兩種模板後，面對任何滑動視窗題目，你的思考流程應該是：「視窗大小固定還是可變？狀態該用 HashMap 還是計數陣列？答案在視窗合法時更新還是在每次移動後更新？」這三個問題能幫你快速鎖定正確實作。
下一篇文章將介紹動態規劃（Dynamic Programming）基礎 — 從記憶化搜尋到遞推公式，解析最優子結構與無後效性，敬請期待。
希望這篇文章能幫助你全面掌握滑動視窗技巧，在面試和實戰中都能靈活運用。如有任何問題或疑惑，歡迎透過 聯絡頁面 與我交流！