🪟 Sliding Window

滑動視窗是一種技巧，用來在陣列或字串上維護一段連續的子區間。透過「右邊擴展、左邊收縮」來避免重複計算，將暴力的 O(n²) 優化到 O(n)。

Notes:

• 視窗大小固定或可變，取決於題目條件
• 常搭配 Hash Map 來追蹤視窗內的元素狀態
• 關鍵在於判斷何時收縮左邊界

兩種視窗

• 擴張 (expand)：右邊界右移，納入新元素。
• 收縮 (shrink)：左邊界右移，移出舊元素。
• 滑動 (slide)：同時擴張與收縮，視窗長度不變。

依「長度是否固定」分成兩套模板。

固定長度視窗

求「所有長度為 k 的子陣列/子字串」的某個極值或統計。視窗滿了就一進一出地滑過去，O(n)。

fun maxSumOfSizeK(nums: IntArray, k: Int): Int {
    var sum = 0
    for (i in 0 until k) sum += nums[i]      // 第一個視窗
    var best = sum
    for (right in k until nums.size) {
        sum += nums[right] - nums[right - k]  // 進一個、出一個
        best = maxOf(best, sum)
    }
    return best
}

動態長度視窗

求「滿足某條件的最長/最短連續區間」。右指針不斷擴張，一旦違反條件就收縮左指針，直到重新合法。

// 範例：最長無重複字元子字串
fun lengthOfLongestSubstring(s: String): Int {
    val window = HashMap<Char, Int>()   // 字元 -> 視窗內次數
    var left = 0
    var best = 0
    for (right in s.indices) {
        val c = s[right]
        window[c] = window.getOrDefault(c, 0) + 1
        while (window[c]!! > 1) {        // 違反「無重複」就收縮
            val d = s[left]
            window[d] = window[d]!! - 1
            left++
        }
        best = maxOf(best, right - left + 1)
    }
    return best
}

延伸：滾動雜湊

固定長度視窗配上「滾動雜湊 (rolling hash)」可在 O(1) 內更新整個視窗的雜湊值（移出最高位、乘基底、加入新字元），用於子字串比對（Rabin–Karp）。這是把滑動視窗從「統計」推廣到「字串指紋比對」的橋樑。

跨倉庫導讀

• 對應理論章節：線性資料結構（陣列雙指針技法）