如何在 Python 中實現滑動視窗

滑動視窗會維持一段連續範圍，並讓這段範圍沿著清單或字串移動。在 Python 中，若每次移動視窗後都能根據前一個視窗更新答案，而不必重新計算所有內容，這種模式就很實用。以下範例介紹三種常見形式：固定大小的視窗、只含不重複字元的可變大小視窗，以及符合目標總和的視窗。

什麼是滑動視窗技巧？

視窗是由左、右位置界定的一段範圍。它可以有固定長度，也可以隨著演算法加入或移除項目而改變長度。視窗中的項目彼此相鄰，因此滑動視窗適用於子陣列和子字串問題；它無法直接表示中間有間隔的任意選取項目。

這種技巧通常能減少重複運算。例如，算出一個視窗的總和後，將視窗向右移一格，只要減去離開視窗的值，再加上新進入視窗的值即可。這次更新只需常數時間。整體複雜度取決於具體演算法及其使用的資料結構，因此滑動視窗不保證能讓每個問題都加速，也不保證每個問題都能在 O(n) 時間內完成。

使用滑動視窗求大小為 K 的子陣列最大總和

給定一串數字和正整數視窗大小 k，先加總前 k 個值。接著每次將視窗向右移一格，利用離開視窗和進入視窗的值更新總和，並記錄目前看過的最大總和。如果 k 不是正數，或大於清單長度，這個範例會回傳 None，明確說明輸入的限制。

對清單 [2, 1, 5, 1, 3, 2] 而言，當 k = 3 時，視窗依序為 [2, 1, 5]、[1, 5, 1]、[5, 1, 3] 和 [1, 3, 2]。程式會印出其中最大的總和。若清單長度為 n，時間複雜度為 O(n)，額外空間複雜度為 O(1)。

def max_sum_subarray(values, k):
    if k <= 0 or k > len(values):
        return None

    window_sum = sum(values[:k])
    best_sum = window_sum

    for right in range(k, len(values)):
        window_sum += values[right] - values[right - k]
        best_sum = max(best_sum, window_sum)

    return best_sum

values = [2, 1, 5, 1, 3, 2]
k = 3
print(max_sum_subarray(values, k))

這段範例程式提供給你自行執行；此處不宣稱已有執行結果。

使用滑動視窗找出沒有重複字元的最長子字串

這個問題要求視窗內不能有重複字元。讓右側位置逐一移過字串，並將每個新字元加入集合。如果新字元已在集合中，就向右移動左側位置，並從集合中移除離開視窗的字元，直到重複字元消失。恢復條件後，再更新目前的最長長度。

每個位置最多只會向前移動一次，每個字元也最多只會加入集合和移出集合各一次。因此，對長度為 n 的字串而言，演算法的時間複雜度為 O(n)，空間複雜度為 O(min(n, 字母表大小))。Python 會逐一處理 Unicode 碼位；使用者感知到的一個字元，例如由基本字母和附加符號組成的字元，可能包含多個碼位。

def longest_unique_substring_length(text):
    window_chars = set()
    left = 0
    best_length = 0

    for right, char in enumerate(text):
        while char in window_chars:
            window_chars.remove(text[left])
            left += 1
        window_chars.add(char)
        best_length = max(best_length, right - left + 1)

    return best_length

text = "abcabcbb"
print(longest_unique_substring_length(text))

這段範例程式提供給你自行執行；此處不宣稱已有執行結果。

使用滑動視窗找出總和至少達到目標的最短子陣列

給定目標總和，這個方法會找出總和至少達到目標的最短連續子陣列。它的前提是所有值都必須為非負數：當目前總和已足夠大時，從左側移除一個值不會讓總和變大，因此可以縮小視窗，找出更短的有效範圍。若含有負數，這套推理就不成立，必須改用其他演算法。

找不到符合條件的子陣列時，函式會回傳 0。當值皆為非負數且目標為正數時，每個位置最多只會加入和移除一次，因此時間複雜度為 O(n)，額外空間複雜度為 O(1)。程式也接受非正數目標並回傳長度為零的答案，因為不需要任何元素就能達到該目標。

def min_subarray_length(target, values):
    if target <= 0:
        return 0

    left = 0
    running_sum = 0
    shortest = len(values) + 1

    for right, value in enumerate(values):
        running_sum += value
        while running_sum >= target:
            shortest = min(shortest, right - left + 1)
            running_sum -= values[left]
            left += 1

    return 0 if shortest > len(values) else shortest

values = [2, 3, 1, 2, 4, 3]
target = 7
print(min_subarray_length(target, values))

這段範例程式提供給你自行執行；此處不宣稱已有執行結果。

結論

滑動視窗能幫助我們思考清單或字串中的連續範圍。範圍大小已知時，使用固定大小的視窗；若範圍由不重複字元或目標總和等條件決定，就依條件調整視窗邊界。採用這種模式前，先確認視窗移動時能否更新所需狀態，以及演算法的前提是否符合輸入資料。這些範例涵蓋常見的 Python 面試題型，但遇到其他限制時，可能需要改用不同的方法。

常見問題

1. 什麼時候適合使用滑動視窗？ 當問題涉及連續的子陣列或子字串，而且移動一側或兩側邊界時可以更新目前結果，就適合考慮使用。
2. 每種滑動視窗演算法的時間複雜度都是 O(n) 嗎？ 不是。這些範例的邊界移動次數和每一步的更新工作都有上限，因此時間複雜度是線性的。其他演算法每次移動視窗時可能需要做更多運算。
3. 這種最小總和視窗可以處理負數嗎？ 依照目前的寫法不行。縮小視窗的規則仰賴所有值皆為非負數；移除負數反而可能讓總和增加。
4. 子陣列和子序列有什麼差別？ 子陣列中的項目必須連續。子序列則可以跳過某些位置，但保留原本的順序，因此滑動視窗無法列舉所有子序列。