Sliding Windows 演算法主要用來處理連續子序列的問題，觀察 window 內部的元素，以及調整 window 的大小以及位置，來讓 window 可以符合所需要的條件。

核心作法

sliding window 會有兩個指標 left 跟 right 來定義這個 window 的範圍

right 的目的是為了讓 window 來探索更多的元素來達到所需要的條件。
left 的目的則是為了收縮 window 的大小，排除不必要的元素。

適用情景

  1. 從序列中尋找包含所需的連續子序列
  2. 求最大/最小長度、總和等優化問題
  3. 具有單調性：擴展窗口會改變某個狀態，收縮窗口可以恢復

常見題型

  1. 找最長/最短的子字串
  2. 找固定條件下的子陣列(如總和等於 k)
  3. 找不包含重複字母的子字串
  4. 找包含特定字母的最小子字串

時間複雜度

  • 暴力解法: $O(n^2)$ ~ $O(n^3)$
  • Sliding Window: $O(n)$ - 每個元素最多被訪問兩次