Python滑動窗口詳解

一、滑動窗口概述

滑動窗口，顧名思義就是一個可以滑動的窗口，它可以用來解決一些數組/字符串的子元素問題。

滑動窗口的核心思想是，定義一些指針和索引來表示一些位置，移動窗口，更新狀態，並且在不遺漏任何位置的前提下，找到我們需要的答案。

那麼，程序員在使用滑動窗口算法時，需要如何思考呢？

首先，一定是定義一個窗口，這個窗口通常是一個連續的子區間，然後用變量 left 和 right 表示窗口的左右邊界，再根據問題的需要定義一些其它變量。然後，窗口開始向右滑動，當窗口右端點右移時，也就是 right += 1 時，窗口中多了一個右邊的元素，窗口的和會發生什麼變化？需要減少還是增加？這部分問題需要我們自己去思考。

二、常用滑動窗口算法題目及解法

1. 最小覆蓋子串

題目描述：給定一個字符串 S 和一個字符串 T，請在 S 中找出包含 T 所有字母的最小子串。

解法：使用雙指針和哈希表。首先使用哈希表記錄下字符串 T 中每個字符出現的次數，然後使用雙指針 left 和 right 來表示窗口的左右邊界。當窗口中包含所有字符時，取最小子串，然後左指針右移，不斷更新最小字符串。當窗口中不包含所有字符時，右指針右移。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:  
            return ""
        
        left, right = 0, 0
        cnt = len(t)
        need = {}
        for i in t:
            need[i] = need.get(i, 0) + 1
        res = ""
        min_len = float("inf")
        
        while right  0:
                    cnt -= 1
                need[s[right]] -= 1
            right += 1
            
            while cnt == 0:
                if (right - left) < min_len:
                    min_len = right - left
                    res = s[left:right]
                if s[left] in need:
                    if need[s[left]] == 0:
                        cnt += 1
                    need[s[left]] += 1
                left += 1
        return res

2. 求和等於K的最長子數組

題目描述：給定一個整數數組 nums 和一個目標值 k，請找到數組中和等於 k 的最長子數組長度。如果不存在任意一個符合條件的子數組，則返回 0。

解法：使用前綴和加哈希表。首先，定義一個哈希表，存儲每個前綴和出現的最早下標。然後，定義一個變量 sum 為前綴和，當 sum – k 在哈希表中存在時，說明從 i 到 j 存在一個子數組和等於 k，將其長度與之前計算的最大長度進行比較，更新答案。

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        if not nums:
            return 0
        
        res = 0
        prefix_sum = 0
        has_dict = {0:-1}
        
        for i in range(len(nums)):
            prefix_sum += nums[i]
            if prefix_sum - k in has_dict:
                res = max(res, i - has_dict[prefix_sum - k])
            if prefix_sum not in has_dict:
                has_dict[prefix_sum] = i
        return res

三、滑動窗口要點總結

1、滑動窗口算法（雙指針算法）是一種固定長度的窗口在數組上滑動，通過雙指針（數組坐標）對數組一個個進行滑動統計，並得出問題的解。

2、滑動窗口的時間複雜度通常為 O(n)，比一般的暴力解法要高效許多。

3、當想要在一個數組或是一個字符串中找到一個子區間，滑動窗口算法應該是一個不錯的選擇。

4、在使用滑動窗口算法的過程中，一定要注意邊界問題，並且稍加思考時，可以使用哈希表等數據結構優化算法。

5、掌握了滑動窗口算法的思想和模板，我們可以針對具體問題進行適當的修改和調整，解決更多的問題。