配列 / 文字列（応用）Sliding Window

LeetCode 練習問題集

問題	難易度	重要度	テクニック
Maximum Average Subarray I	★★	高	Fixed Size Sliding Window
K Radius Subarray Averages	★★	高	Fixed Size Sliding Window
Sliding Subarray Beauty	★★★	高	Fixed Size Sliding Window
Longest Substring Without Repeating Characters	★★★	高	Variable Sized Sliding Window
Fruit Into Baskets	★★★	高	Variable Sized Sliding Window
Longest Repeating Character Replacement	★★★	高	Variable Sized Sliding Window
Minimum Size Subarray Sum	★★★	高	Variable Sized Sliding Window
Minimum Window Substring	★★★★	中	Variable Sized Sliding Window

Sliding WIndowは、配列・リスト・文字列のようなデータ構造に対する部分配列（文字列）に焦点をあててオーバーラップする計算を最適化する事ができます。このアルゴリズムは、1つの "Window" (部分配列や部分文字列)を連続的に "スライド" することで、そのWindow内の要素に対する計算（例えば、最大/最小の要素を見つける、合計または平均を計算するなど）を効率的に行うことができます。

Sliding Windowには主に2つの方式があり

• Fixed Size Sliding Window : 固定のWindowサイズで、そのサイズを維持しながらWindowをスライドさせ、各ステップで必要な計算を行います。例えば、固定長の部分配列の最大合計を求める場合などに用いられます。
• Variable Sized Sliding Window : 動的なWindowサイズで、条件に応じてWindowのサイズを調整しながらスライドさせます。例えば、特定の合計を超える最小の部分配列を見つける場合などに適しています。

Max Subarray Sum - Fixed Size Sliding Window

難易度:★★ 重要度: 高