滑動窗口方法

3.1 定義滑動窗口方法。

滑動窗口方法（Sliding Window） 是一種技巧， 用於解決數組或字符串問題。這種技術通過在數據上移動固定的子數組（或子字符串）， 以尋找最佳解決方案。這樣可以處理固定大小窗口內的元素， 並根據問題條件動態改變窗口大小。

這種技術在涉及數據序列的問題上特別有用，比如數組或字符串， 並幫助減少與更簡單方法相比的時間複雜度。

基本原則

• 初始化窗口: 設置窗口的開始和結束位置到初始位置。
• 移動窗口: 逐步移動窗口邊界， 從一側添加元素並從另一側刪除元素。
• 處理窗口: 在每一步中，對當前窗口執行必要的計算。

滑動窗口方法的時間和空間複雜度

時間複雜度:

• O(n) — 大多數情況下，因為指針或窗口沿著數組線性移動，檢查每個可能的窗口位置。

空間複雜度:

• O(1) — 如果使用固定數量的額外內存來存儲當前值。
• O(k) — 如果需要存儲當前窗口大小為 k 的元素。

3.2 尋找最大子數組和。

尋找固定大小的最大子數組和

問題:

找到固定大小的子數組 k，使其和最大。

解決方案:

使用滑動窗口方法來維持當前子數組的和， 並在窗口移動時更新最大和。

時間複雜度: O(n).

Python 示例代碼:

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1
            
    window_sum = sum(arr[:k])
    max_sum = window_sum
            
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
            
    return max_sum
        

3.3 在字符串中尋找所有子字符串的異序詞

問題:

找到一個給定子字符串 p 在字符串 s 中的所有異序詞。

解決方案:

使用滑動窗口方法來維持當前窗口的字符頻率字典， 並將其與子字符串的頻率字典進行比較。

時間複雜度: O(n).

Python 示例代碼:

from collections import Counter

def find_anagrams(s, p):
    p_count = Counter(p)
    s_count = Counter()
                
    result = []
    k = len(p)
                
    for i in range(len(s)):
        s_count[s[i]] += 1
        
        if i >= k:
            if s_count[s[i - k]] == 1:
                del s_count[s[i - k]]
            else:
                s_count[s[i - k]] -= 1
                            
        if s_count == p_count:
            result.append(i - k + 1)

    return result

3.4 尋找最小子數組

尋找和超過給定值的最小子數組

問題:

找到和超過給定值 S 的最小子數組。

解決方案:

使用滑動窗口方法來擴展右邊界，直到和大於 S， 然後移動左邊界以最小化子數組的長度。

時間複雜度: O(n).

Python 示例代碼:

def min_subarray_len(S, arr):
    n = len(arr)
    min_len = float('inf')
    current_sum = 0
    left = 0
            
    for right in range(n):
        current_sum += arr[right]
                
        while current_sum >= S:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
            
    return 0 if min_len == float('inf') else min_len