スライディングウィンドウとは
配列のサブアレイを”ウィンドウ（サブセット）”をずらすしていくように探索するアルゴリズム。
ウィンドウサイズは固定または動的。
実例としては、レートリミッターで使われたりする。
実装
ソースコードは以下。
与えられた配列から合計がN以上になるサブアレイを探索する関数。
package main
import "fmt"
func SlidingWindow(s []int, sum int) [][]int {
rslt := [][]int{}
windowSum := 0
windowStart := 0
for windowEnd := 0; windowEnd < len(s); windowEnd++ {
windowSum += s[windowEnd]
// サブアレイを見つける
for windowSum >= sum {
rslt = append(rslt, s[windowStart:windowEnd+1])
windowSum -= s[windowStart]
windowStart++
}
}
return rslt
}
func main() {
s := []int{1, 3, 2, 6, 4, 9, 9, 5}
sum := 9
subAry := SlidingWindow(s, sum)
for _, sa := range subAry {
fmt.Println(sa)
}
}
// 出力
[1 3 2 6]
[3 2 6]
[2 6 4]
[6 4]
[4 9]
[9]
[9]
SlidingWindow関数の処理の流れとしてはこんな感じ。
- データの先頭から開始位置までウィンドウを配置
- ウィンドウ内の要素が条件を満たすかどうかを確認
- 条件を満たす場合、ウィンドウ内のサブアレイを結果に追加
- ウィンドウを右に1段階スライド
- ウィンドウがデータの終わりに達するまで、手順 3 ～ 5 を繰り返す
ウィンドウがずれていくイメージが次の通り。
[1 3 2 6] ← 最初に見つかった条件を満たすウィンドウ
[3 2 6] ←条件を満たすウィンドウ内で更に探索
[2 6 4] ←探索開始位置をズラして次のウィンドウを確保
[6 4] ←ウィンドウ内を更に探索
以下繰り返し・・・
[4 9]
[9]
[9]
配列を扱う問題で応用が効く。
最適解ではないが、leetcode.com - two-sumはスライディングウィンドウを使って解くこともできる。
追記
この動画が分かりやすかった。
youtube.com - Solve subarray problems FASTER (using Sliding Windows)
ウインドウサイズが固定の場合、動的な場合の解説がある。
参考
- www.techinterviewhandbook.org - Array cheatsheet for coding interviews
itnext.io - Sliding Window Algorithm Technique
