スライディングウィンドウ

スライディングウィンドウは、移動する区間を使って条件を満たす連続部分配列を探します。このレッスンでは、和が目標以上になる最短の部分配列を求めます。右端で要素を追加し、条件を満たしたら左端から除いて短くします。要素は非負、目標は正数が前提です。時間計算量は O(n)、追加領域は O(1) です。

配列に沿って動く定規を考えます。右端を伸ばし、条件を満たしたら左端を縮めます。両端とも右へ進むだけで、前の位置に戻りません。各要素を最大一回追加し、一回除くため、処理は線形時間になります。

スライディングウィンドウの仕組み

区間 [left, right] と、その要素の和 total を保持します。right を先頭から末尾へ進め、まず nums[right] を total に加えます。これで窓が右へ一セル広がります。

total >= target の間は、現在の長さを候補として記録してから、nums[left] を引いて left を右へ進めます。まだ条件を満たすなら、さらに縮めます。和が目標未満になったら収縮を止め、右端で次の要素を追加します。

全体で right は n 回進みます。left も前進するだけで、各要素を最大一回除くため、最大 n 回です。合計移動回数は 2n 以下で、n(n+1)/2 個の部分配列をすべて調べる必要はありません。プレイヤーの edges advanced は、この移動回数を数えます。

非負の値なら、拡張しても和は減らず、収縮しても和は増えません。負数があると、除去によって和が増える場合があり、収縮を止める判断が短い答えを見落とす原因になります。

スライディングウィンドウのステップ

初期入力は nums = [2, 3, 1, 2, 4, 3]、target = 7 です。left = 0、total = 0 から始め、最良の長さはまだありません。

1. right = 0：2 を追加し、窓は [0, 0]、total = 2 < 7 です。拡張を続けます。
2. right = 1：3 を追加し、窓は [0, 1]、total = 5 です。拡張を続けます。
3. right = 2：1 を追加し、窓は [0, 2]、total = 6 です。拡張を続けます。
4. right = 3：2 を追加し、窓は [0, 3]、total = 8 です。初めて条件を満たし、best = 4 を記録します。nums[0] = 2 を除くと、total = 6、left = 1 になり、収縮を止めます。
5. right = 4：4 を追加し、窓は [1, 4]、total = 10 です。長さはまだ 4 です。nums[1] = 3 を除くと、total = 7、left = 2 になります。窓 [2, 4] の長さ 3 で best = 3 に更新します。さらに nums[2] = 1 を除くと、total = 6、left = 3 になり、収縮を止めます。
6. right = 5：3 を追加し、窓は [3, 5]、total = 9 です。長さ 3 では最良値は変わりません。nums[3] = 2 を除くと、total = 7、left = 4 です。窓 [4, 5] の長さ 2 で best = 2 に更新します。さらに nums[4] = 4 を除くと、total = 3、left = 5 になり、収縮を止めます。

右端が末尾に達したので終了します。答えは添字 4、5 の [4, 3]、長さ 2 です。六回の拡張と五回の収縮で、移動は十一回です。総当たりなら 6 · 7 / 2 = 21 個の部分配列が候補になります。

アニメーションの枠は現在の窓、上の数値は和を表します。目標に達すると和の表示が琥珀色から緑に変わります。最良の長さは 4、3、2 の順に小さくなります。

時間・空間計算量

この実装は長さ 1 を見つけても残りを走査します。両端の合計移動回数は 2n 以下なので、いずれも O(n) です。二つの添字、和、最良の答えだけを保持し、追加領域は O(1) です。

負数を許す同じ問題には、累積和と単調両端キューを使えます。時間は O(n)、追加領域は O(n) で、LeetCode #862 に相当します。幅が固定された窓では、毎回一要素を追加し一要素を除くだけです。条件を満たす間に縮める可変幅の処理とは異なります。

境界条件

• 一要素で目標に達する：長さ 1 が得られます。空でない部分配列の最短長です。
• 条件を満たす部分配列がない：収縮せず、best は未定義のままなので 0 を返します。
• 全配列だけが条件を満たす：全長まで拡張し、左端を一つ除くと和が不足します。答えは n です。
• 空配列：ループを実行せず 0 を返します。
• 重複値・ゼロ：通常どおり処理します。ゼロで和が変わらなくても、収縮のたびに左端は進みます。

よくある間違い

• 負数にも同じ規則を使う：[3, -2, 5]、目標 4 では長さ 3 を返しますが、[5] の長さ 1 で足ります。3 を除いた和が 3 になって収縮を止めるため、続く −2 を除けません。負数を含むシナリオでこの反例を確認できます。
• while を if にする：一回の拡張で、複数回の収縮が必要な場合があります。一要素だけ除くと、窓を縮めきれません。
• 収縮してから長さを記録する：記録時点で窓が条件を満たす必要があります。先に nums[left] を引くと、無効な窓を答えにする場合があります。
• ポインタを後退させる：right を進めるたびに left を 0 に戻すと、同じ要素を何度も処理し、O(n) の保証を失います。
• 固定幅の問題で可変幅の処理を使う：幅 k が固定なら、入る要素と出る要素を管理するだけです。条件を満たす間の収縮は不要です。