1. 概要

特定の配列内のいくつかの範囲の答えをチェックする必要がある問題を処理する場合、スライディングウィンドウアルゴリズムは非常に強力な手法になります。

このチュートリアルでは、スライディングウィンドウの手法と、そのバリエーションである固定ウィンドウサイズと柔軟ウィンドウサイズの両方について説明します。 また、理解を深めるために、両方のバリアントの例を示します。

2. 理論的アイデア

スライディングウィンドウ手法の背後にある主なアイデアは、2つのネストされたループを1つのループに変換することです。 通常、この手法は、時間計算量をからに減らすのに役立ちます。

スライディングウィンドウ手法を使用するための条件は、問題が、配列からの範囲のセットに対して繰り返し答えを計算する関数の最大（または最小）値を見つけることを要求することです。 つまり、これらの範囲を開始に基づいて並べ替えることができ、それらの範囲も並べ替えられる場合は、スライディングウィンドウ手法を使用できます。

言い換えれば、次のことが成り立つ必要があります。

その場合、ここで、およびはいくつかの範囲の左側であり、およびは同じ範囲の左端です。

基本的に、この手法では、2つのポインターとを保持する配列を反復処理できます。 これらのポインタは、現在の範囲の左端と右端を示します。 各ステップで、、、または両方を次の範囲に移動します。

これを行うには、前進するときに現在の範囲に要素を追加できる必要があります。 また、前進するときに現在の範囲から要素を削除できる必要があります。 範囲に到達するたびに、現在の範囲内にある要素からその答えを計算します。

範囲の長さが固定されている場合、これを固定サイズのスライディングウィンドウ手法と呼びます。 ただし、範囲の長さが変更された場合、これを柔軟なウィンドウサイズの手法と呼びます。 これらの両方のオプションの例を示します。

3. 固定サイズのスライディングウィンドウ

この考えをよりよく理解するために例を見てみましょう。

3.1. 問題

問題が長さと数の配列を与えると仮定します。 この問題は、配列内の連続する要素の最大合計を見つけることを求めています。

つまり、最初に、配列内の長さのすべての範囲の合計を計算する必要があります。 その後、計算されたすべての合計の中で最大の合計を返す必要があります。

3.2. 素朴なアプローチ

この問題を解決するための素朴なアプローチを見てみましょう。

まず、範囲のすべての可能な開始を繰り返します。 範囲ごとに、からまでの要素を反復処理し、それらの合計を計算します。 各ステップの後に、これまでのベストアンサーを更新します。 最後に、答えは古い答えと現在計算されている合計の間の最大値になります。

最終的に、すべての範囲の中で見つけた最良の答えを返します。

時間計算量は最悪の場合です。ここで、は配列の長さです。

3.3. スライディングウィンドウアルゴリズム

より複雑にするために、私たちの素朴なアプローチを改善してみましょう。

まず、2つの連続する範囲ごとの関係を見つけましょう。 最初の範囲は明らかにです。 ただし、2番目の範囲はになります。

最初の範囲から2番目の範囲に移動するために2つの操作を実行します。最初の操作は、インデックス付きの要素を回答に追加することです。 2番目の操作は、回答からインデックス1の要素を削除することです。

毎回、対応する範囲の答えを計算した後、計算された合計答えを最大化するだけです。

説明されている問題の解決策を見てみましょう。

まず、最初の範囲の合計を計算します。 次に、これまでの回答としてその合計を保存します。

その後、範囲内にある範囲の可能な端を繰り返し処理します。 各ステップで、現在の範囲の合計を更新します。 したがって、インデックスの要素の値を追加し、インデックスの要素の値を削除します。

毎回、これまでに見つけたベストアンサーを更新して、元のアンサーと新しく計算された合計の間の最大値になります。 最終的に、テストしたすべての範囲の中で見つけた最良の答えを返します。

説明されているアプローチの時間計算量はです。ここで、は配列の長さです。

4. フレキシブルサイズのスライディングウィンドウ

フレキシブルサイズのスライディングウィンドウ手法を2ポインター手法と呼びます。 この手法の例を取り上げて、それをよりよく説明します。

4.1. 問題

本が一列に並んでいるとしましょう。 それぞれの本について、私たちはそれを読むのに必要な分数を知っています。 ただし、読むのに自由な時間しかありません。

また、列からいくつかの連続した本を読む必要があります。 つまり、列に並んでいる本から範囲を選んで読むことができます。 もちろん、本を読むのに必要な時間の合計がを超えてはならないという条件があります。

したがって、問題は私たちが読むことができる本の最大数を見つけることを私たちに求めています。 つまり、配列から、この範囲の長さが可能な限り最大になるような合計の範囲を見つける必要があります。

4.2. 素朴なアプローチ

問題を解決するための素朴なアプローチを見てみましょう。

まず、これまでのベストアンサーをゼロで初期化します。 次に、範囲のすべての可能な開始を繰り返します。 初めごとに、さらに本を読むことができる限り、前に進みます。 これ以上本を読むことができなくなったら、古い本と見つけた範囲の長さの間の最大値まで、ベストアンサーを更新します。

最終的に、私たちは見つけた最良の答えを返します。

このアプローチの複雑さはです。ここで、は本の配列の長さです。

4.3. スライディングウィンドウアルゴリズム

線形の複雑さを得るために、素朴なアプローチを改善しようとします。

まず、配列の先頭から始まる範囲の答えを見つけることができたとしましょう。 次の範囲は、配列内の2番目のインデックスから始まります。 ただし、2番目の範囲の終わりは確かに最初の範囲の終わりの後にあります。

これは、2番目の範囲が最初の要素を使用しないためです。 したがって、2番目の範囲は、使用できる空き時間が増えるため、その終わりをさらに拡張できます。

したがって、ある範囲から別の範囲に移動するときは、最初に現在の回答から古いものを削除します。 また、現在の範囲の終わりを可能な限り拡張しようとします。

したがって、最終的には、考えられるすべての範囲を反復処理し、見つかった最良の回答を保存します。

次のアルゴリズムは、説明されたアイデアに対応しています。

素朴なアプローチと同じように、範囲のすべての可能な始まりを繰り返します。 最初に、現在の合計からインデックスの値を減算します。

その後、可能な限り移動を試みます。 したがって、合計が最大である限り、移動を続けます。 最後に、これまでのベストアンサーを更新します。 現在の範囲の長さはであるため、この値でベストアンサーを最大化します。

アルゴリズムは複雑に見えるかもしれませんが、アルゴリズムを注意深く調べてみましょう。 変数は常にその値を保持します。 したがって、の値に達するまで前進するだけです。 したがって、whileループを合計で実行する回数はほとんどの場合です。

したがって、説明されているアプローチの複雑さはです。ここで、は配列の長さです。

5. 違い

主な違いは、いくつかの問題では、同じサイズのすべての範囲の中で特定のプロパティをチェックするように求められるという事実にあります。 一方、その他の問題については、特定の条件を満たすすべての範囲の中から特定のプロパティを確認するように求められます。 このような場合、この条件により、範囲の長さが変化する可能性があります。

これらの範囲のサイズが既知の場合（連続要素の問題など）、固定サイズのスライディングウィンドウ手法を使用します。 ただし、範囲のサイズが異なる場合（本の長さの問題のように）、柔軟なサイズのスライディングウィンドウ手法を使用します。

また、最初に説明したスライディングウィンドウ手法を使用する場合は、次の条件を常に念頭に置いてください。ポインタを前方に移動すると、その位置を維持するか、前方に移動することを保証する必要があります。

6. 結論

このチュートリアルでは、スライディングウィンドウアプローチについて説明しました。 この手法の理論的アイデアを提供しました。 また、固定サイズとフレキシブルサイズのスライディングウィンドウ手法の2つの例について説明しました。 最後に、各手法をいつ使用するかを説明しました。