スライディングウィンドウとは
配列のサブアレイを”ウィンドウ（サブセット）”をずらすしていくように探索するアルゴリズム。
ウィンドウサイズは固定または動的。
実例としては、レートリミッターで使われたりする。
実装
ソースコードは以下。
与えられた配列から合計がN以上になるサブアレイを探索する関数。
SlidingWindow関数の処理の流れとしてはこんな感じ。
- データの先頭から開始位置までウィンドウを配置
- ウィンドウ内の要素が条件を満たすかどうかを確認
- 条件を満たす場合、ウィンドウ内のサブアレイを結果に追加
- ウィンドウを右に1段階スライド
- ウィンドウがデータの終わりに達するまで、手順 3 ～ 5 を繰り返す
ウィンドウがずれていくイメージが次の通り。
配列を扱う問題で応用が効く。
最適解ではないが、leetcode.com - two-sumはスライディングウィンドウを使って解くこともできる。
追記
この動画が分かりやすかった。
youtube.com - Solve subarray problems FASTER (using Sliding Windows)
ウインドウサイズが固定の場合、動的な場合の解説がある。