前段時間忙于寫系列文章，怒刷算法題的進度算是耽誤了不少。剛好遇到了一道需要滑動窗口的題目，做完之后覺得挺有意思，有必要好好聊一下滑動窗口。
所謂滑動窗口（slide window）是一種優(yōu)化算法的抽象概念，主要于解決數(shù)組、字符串等線性結(jié)構(gòu)中的子數(shù)組或子序列問題。它的整個思路是通過維護一個窗口（window）在數(shù)組上滑動，每次滑動一個單元距離，從而減少重復(fù)計算。
滑動窗口一般分為2種：

固定大小窗口：窗口的大小是固定的，通過移動窗口在數(shù)組或字符串上的位置來解決問題。例如：求數(shù)組種固定長度子數(shù)組的最大和。

可變大小窗口：根據(jù)條件動態(tài)增大或者縮小窗口。例如：求不超過給定和的最大子數(shù)組。

對于固定大小窗口問題，最典型的就是leetCode第三十題：

給定一個字符串 s 和一個包含多個長度相同的單詞的數(shù)組 words，要求找出 s 中所有的起始索引，這些起始索引所對應(yīng)的子串正好是 words 中所有單詞的串聯(lián)排列（順序不限定，但每個單詞必須用一次）。

示例：

輸入：
s = "barfoothefoobarman"
words = ["foo", "bar"]

輸出：
[0, 9]

解釋：
從索引 0 的子串是 "barfoo"，它是 ["foo", "bar"] 的串聯(lián)。
從索引 9 的子串是 "foobar"，它也是 ["foo", "bar"] 的串聯(lián)。

利用滑動窗口，可以很容易實現(xiàn)如下代碼：

from collections import Counter
from typing import List

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []

        word_len = len(words[0])
        word_count = len(words)
        total_len = word_len * word_count
        word_freq = Counter(words)
        result = []

        # 只遍歷 word_len 次
        for i in range(word_len):
            left = i
            right = i
            seen = Counter()
            matched_count = 0

            while right + word_len <= len(s):
                # 提取當(dāng)前單詞
                word = s[right:right + word_len]
                right += word_len

                if word in word_freq:
                    seen[word] += 1
                    matched_count += 1

                    # 如果當(dāng)前單詞出現(xiàn)次數(shù)超過了預(yù)期，移動左指針
                    while seen[word] > word_freq[word]:
                        left_word = s[left:left + word_len]
                        seen[left_word] -= 1
                        matched_count -= 1
                        left += word_len

                    # 如果匹配的單詞數(shù)量等于 words 中的單詞數(shù)量，記錄起始索引
                    if matched_count == word_count:
                        result.append(left)
                else:
                    # 當(dāng)前單詞不在 words 中，重置窗口
                    seen.clear()
                    matched_count = 0
                    left = right

        return result

在上述的代碼中，定義了left和right兩個指針，不斷地移動left和right的位置，來讓窗口中的字符串符合條件。當(dāng)單詞出現(xiàn)的頻率大于預(yù)期的數(shù)量，則把left變量向右移動一個單詞長度（word_len)，并且減少seen變量中對應(yīng)單詞的數(shù)量，同時減少matched_count。

當(dāng)遇到不在規(guī)定中的單詞，則重置整個窗口。

這里第一個循環(huán)比較取巧，只循環(huán)單詞長度（word_len)就能遍歷出所有的不重復(fù)結(jié)果。

第二個例子是大小不固定的窗口案例，題目是：

求數(shù)組中和不超過 k 的最大長度子數(shù)組。

def get_max_sub_arry_length(nums: List[int], k: int) -> int:
    left = 0
    max_length = 0
    sum = 0
    for right in range(len(nums)):
        # 擴大窗口
        sum += nums[right]

        while sum > k and left <= right:
            # 縮小窗口
            sum -= nums[left]
            left += 1
        # 重新計算最大長度
        max_length = max(max_length, right - left + 1)
    
    return max_length

nums = [1,2,3,4,5]
k = 8
print(get_max_sub_arry_length(nums, k))