滑動窗口算法簡介

滑動窗口是一種用于處理數組或字符串子區間問題的高效算法。它通過維護一個動態窗口（通常由兩個指針表示）來避免重復計算，將時間復雜度從O(n2)優化到O(n)。

基本實現步驟

1. 初始化窗口指針：通常使用left和right指針表示窗口的左右邊界。
2. 移動右指針：逐步擴展窗口，直到滿足特定條件（如窗口內元素和達到目標值）。
3. 調整左指針：當條件滿足時，收縮窗口以尋找更優解或繼續下一輪搜索。

示例代碼

以下是一個求“和大于等于目標值的最短子數組長度”的滑動窗口實現：

public int minSubArrayLen(int target, int[] nums) {int left = 0, sum = 0;int minLength = Integer.MAX_VALUE;for (int right = 0; right < nums.length; right++) {sum += nums[right];while (sum >= target) {minLength = Math.min(minLength, right - left + 1);sum -= nums[left++]; // 收縮窗口}}return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

常見應用場景

• 固定窗口大小：如計算大小為k的子數組的平均值。
• 可變窗口大小：如尋找滿足條件的最短/最長子數組。
• 字符串匹配：如找到包含所有目標字符的最小窗口。

注意事項

• 邊界條件：處理空數組或無法滿足條件的情況。
• 負數處理：若數組包含負數，滑動窗口可能失效，需改用其他方法（如前綴和+哈希表）。
• 復雜度分析：確保每個元素最多被訪問兩次（O(n)時間復雜度）。

變式問題

• 無重復字符的最長子串（LeetCode 3）：使用哈希表記錄字符最后出現位置。
• 最大連續1的個數 III（LeetCode 1004）：通過計數允許的翻轉次數來維護窗口。