Sliding Window

預備知識

Two Pointers

滑動視窗（Sliding Window）是 Two Pointers 的一種特殊應用，專門用來處理 「連續」子陣列或子字串的問題。

它維護一個左右邊界（也就是一段連續的區間，稱為 Window），讓這個區間像窗戶一樣在陣列上移動，藉此避免對每一種可能的子區間都重新計算一次，把原本 O(n^2) 甚至 O(n^3) 的暴力解降到 O(n)。

白話理解

想像坐火車看窗外風景，車廂的窗戶（Window）固定大小，隨著火車前進，窗戶裡看到的風景會持續「新增前方的景色、移除後方已經看過的景色」，而不需要每次都把整條鐵路重新看一遍。

兩種類型

1. Fixed Size Window（固定大小視窗）

視窗大小固定，只需要一路往右滑動。

範例：找出陣列中「連續 k 個數字」的最大總和。

Python
JavaScript
Java

def max_subarray_sum(arr, k):
    window_sum = 0

    # 先計算第一個視窗（前 k 個元素）的總和
    for i in range(k):
        window_sum += arr[i]

    max_sum = window_sum

    # 視窗往右滑動一格：加入新進來的元素，扣掉被擠出去的元素
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

function maxSubarraySum(arr, k) {
  let windowSum = 0;

  // 先計算第一個視窗（前 k 個元素）的總和
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }

  let maxSum = windowSum;

  // 視窗往右滑動一格：加入新進來的元素，扣掉被擠出去的元素
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

class Solution {
    public static int maxSubarraySum(int[] arr, int k) {
        int windowSum = 0;

        // 先計算第一個視窗（前 k 個元素）的總和
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }

        int maxSum = windowSum;

        // 視窗往右滑動一格：加入新進來的元素，扣掉被擠出去的元素
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i] - arr[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }
}

逐步拆解：以 `arr = [2, 1, 5, 1, 3, 2]`、`k = 3` 為例

視窗範圍	windowSum	說明
`[2, 1, 5]`	8	初始視窗（前 3 個元素），maxSum = 8
`[1, 5, 1]`	8 - 2 + 1 = 7	扣掉滑出去的 `2`，加上滑進來的 `1`
`[5, 1, 3]`	7 - 1 + 3 = 9	maxSum 更新為 9
`[1, 3, 2]`	9 - 5 + 2 = 6	沒有超過目前的 maxSum

最終答案是 9。整個過程完全不需要重新加總整個視窗，只需要「加一個、減一個」，這正是 Sliding Window 比暴力法快的關鍵。

2. Variable Size Window（動態大小視窗）

視窗大小會依條件伸縮：先擴張右邊界，直到不符合條件，再收縮左邊界。

範例：Leetcode: Longest Substring Without Repeating Characters，找出字串中最長「不重複字元」的連續子字串長度。

Python
JavaScript
Java

def length_of_longest_substring(s):
    seen = {}  # 記錄每個字元「上一次出現」的 index
    left = 0
    max_length = 0

    for right in range(len(s)):
        char = s[right]

        # 如果這個字元曾經出現過，且出現位置在目前視窗範圍內，就把左邊界收縮到重複字元的下一格
        if char in seen and seen[char] >= left:
            left = seen[char] + 1

        seen[char] = right
        max_length = max(max_length, right - left + 1)

    return max_length

function lengthOfLongestSubstring(s) {
  const seen = new Map(); // 記錄每個字元「上一次出現」的 index
  let left = 0;
  let maxLength = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];

    // 如果這個字元曾經出現過，且出現位置在目前視窗範圍內，就把左邊界收縮到重複字元的下一格
    if (seen.has(char) && seen.get(char) >= left) {
      left = seen.get(char) + 1;
    }

    seen.set(char, right);
    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
}

import java.util.HashMap;
import java.util.Map;

class Solution {
    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> seen = new HashMap<>(); // 記錄每個字元「上一次出現」的 index
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);

            // 如果這個字元曾經出現過，且出現位置在目前視窗範圍內，就把左邊界收縮到重複字元的下一格
            if (seen.containsKey(c) && seen.get(c) >= left) {
                left = seen.get(c) + 1;
            }

            seen.put(c, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

新手小提醒

動態視窗的核心口訣是：先無腦擴張右邊界，發現不符合條件了，才收縮左邊界。收縮時要用 while（可能需要連續收縮好幾次）而不是 if（只收縮一次），視題目條件而定；上面這題因為一次只會有一個重複字元，用 if 也足夠。

複雜度

類型	時間複雜度	空間複雜度
Fixed Size Window	O(n)	O(1)
Variable Size Window	O(n)	視情況而定，通常是 O(k)（k 為視窗內需要記錄的相異元素種類數）

雖然動態視窗看起來像雙層迴圈（右指標一層、左指標一層），但因為左指標一輩子最多只會往右移動 n 次，整體還是 O(n) 而不是 O(n^2)。

適用情況

固定長度的連續子區間統計：例如固定視窗大小的最大/最小總和、平均值。
尋找符合條件的最長 / 最短連續子區間：例如不重複字元的最長子字串、和至少為 k 的最短子陣列。
字元出現次數限制類問題：例如「最多可以替換 k 個字元」的最長重複字元子字串，通常會搭配一個 Hash Table 或固定大小的陣列來記錄視窗內的字元次數。

常見誤區

該用 Variable Window 卻用 Fixed Window：如果題目要求「找出符合條件的區間，但長度不確定」，代表要用動態視窗，先確認題目問的是「固定長度」還是「最長 / 最短」。
收縮視窗的時機寫錯：忘記在右邊界擴張「之後」才檢查是否需要收縮左邊界，或是該用 while 卻寫成 if，導致視窗內殘留不符合條件的元素。
忘記同步更新輔助的統計資料：視窗左右邊界移動時，如果視窗內用了額外的 Hash Map 或計數陣列記錄元素出現次數，必須同步在「新增進視窗」與「移出視窗」時更新，忘記其中一邊會讓統計資料失真。
和 Prefix Sum 搞混使用時機：如果題目需要「多次查詢」任意（不一定連續變動的）區間和，Prefix Sum 通常更合適；Sliding Window 則更適合「視窗會隨條件連續變化」的場景。

兩種類型​

1. Fixed Size Window（固定大小視窗）​

逐步拆解：以 arr = [2, 1, 5, 1, 3, 2]、k = 3 為例​

2. Variable Size Window（動態大小視窗）​

複雜度​

適用情況​

常見誤區​