スライディング ウィンドウ問題は、要素の連続サブセットに基づいて問題を効率的に解決するために、固定サイズまたは可変サイズのウィンドウをデータ構造 (通常は配列または文字列) 内で移動させる問題です。この手法は、指定された一連の条件に従って部分配列または部分文字列を検索する必要がある場合に使用されます。
スライディング ウィンドウ技術
目次
- スライディングウィンドウテクニックとは何ですか?
- スライディングウィンドウテクニックの使い方は？
- スライディング ウィンドウの問題を特定する方法
- スライディング ウィンドウ手法の使用例
- スライディング ウィンドウ手法の練習問題
スライディングウィンドウテクニックとは何ですか?
スライディング ウィンドウ技術 の定義を伴う問題を効率的に解決するために使用される方法です。 窓 または 範囲 入力データ (配列または文字列) 内でウィンドウを移動し、ウィンドウ内で何らかの操作を実行します。この手法は、特定の合計を持つ部分配列の検索、一意の文字を含む最長の部分文字列の検索、要素を効率的に処理するために固定サイズのウィンドウを必要とする問題の解決などのアルゴリズムでよく使用されます。
これを正しく理解するために例を挙げてみましょう。サイズの配列があるとします。 N そして整数も K. ここで、正確なサイズの部分配列の最大合計を計算する必要があります。 K. さて、この問題にどのようにアプローチすべきでしょうか?
これを行う 1 つの方法は、配列からサイズ K の各部分配列を取得し、これらの部分配列の最大合計を見つけることです。これは、ネストされたループを使用して実行でき、結果は O(N2) 時間の複雑さ。
しかし、このアプローチを最適化できるでしょうか?
答えは「はい」です。 K サイズのサブ配列を作成してその合計を計算するには、0 から K-1 インデックスまでの 1 つの K サイズのサブ配列を取得し、その合計を計算します。次の反復で左と左を増やすように、反復とともに範囲を 1 つずつシフトして結果を更新します。右ポインタを右クリックして、以下の図に示すように前の合計を更新します。
スライディング ウィンドウ技術
次に、配列の最後に到達するまで、反復ごとにこのメソッドに従います。
スライディング ウィンドウ技術
キャット・ティンプの体重はどれくらいですか
したがって、サイズ K の各部分配列の合計を再計算する代わりに、サイズ K の前のウィンドウを使用し、その結果を使用して合計を更新し、左右のポインターを移動してウィンドウを右にシフトしていることがわかります。この操作は最適です。再計算する代わりに範囲を移動するには O(1) 時間がかかります。
ポインタを移動し、それに応じて結果を計算するこのアプローチは、 スライディングウィンドウ技術 。
スライディングウィンドウテクニックの使い方は？
スライディング ウィンドウには基本的に 2 つのタイプがあります。
1. 固定サイズのスライディング ウィンドウ:
これらの質問を解決するための一般的な手順は、次のとおりです。
- 必要なウィンドウのサイズを見つけます (K とする)。
- 最初のウィンドウの結果を計算します。つまり、データ構造の最初の K 要素が含まれます。
- 次に、ループを使用してウィンドウを 1 ずつスライドさせ、ウィンドウごとに結果を計算し続けます。
2. 可変サイズのスライディング ウィンドウ:
これらの質問を解決するための一般的な手順は、次のとおりです。
- このタイプのスライディング ウィンドウ問題では、条件が true になるまで右ポインタを 1 つずつ増やします。
- いずれのステップでも、条件が一致しない場合は、左ポインタを大きくしてウィンドウのサイズを縮小します。
- 繰り返しますが、条件が満たされたら、右のポインタを増加し始め、ステップ 1 に従います。
- 配列の最後に到達するまで、次の手順を実行します。
スライディング ウィンドウの問題を特定する方法:
- これらの問題では通常、最大値/最小値を求める必要があります。 サブアレイ 、 部分文字列 ある特定の条件を満たすもの。
- 部分配列または部分文字列のサイズ K’ 一部の問題で出題されます。
- これらの問題は O(N2) ネストされたループを使用した時間計算量、スライディング ウィンドウを使用してこれらを解決できます。 の上） 時間の複雑さ。
- 必要な時間計算量: O(N) または O(Nlog(N))
- 制約: N <= 106, N が配列/文字列のサイズの場合。
スライディング ウィンドウ手法の使用例:
1. サイズ K のすべての部分配列の最大合計を求めるには、次のようにします。
サイズの整数の配列が与えられた場合 「ん」、 私たちの目的は、次の最大合計を計算することです。 「k」 配列内の連続した要素。
入力: arr[] = {100, 200, 300, 400}、k = 2
出力: 700入力: arr[] = {1、4、2、10、23、3、1、0、20}、k = 4
出力: 39
サイズ 4 の部分配列 {4, 2, 10, 23} を追加することで最大の合計を取得します。入力: arr[] = {2, 3}、k = 3
出力: 無効
配列全体のサイズが 2 であるため、サイズ 3 のサブ配列はありません。
素朴なアプローチ: それでは、問題を分析してみましょう ブルートフォースアプローチ 。最初のインデックスから始めて、次のインデックスまで合計します。 k番目 要素。これを、考えられるすべての連続ブロックまたは k 要素のグループに対して実行します。このメソッドにはネストされた for ループが必要です。外側の for ループは k 要素のブロックの開始要素から始まり、内側またはネストされたループは k 番目の要素まで加算されます。
上記のアプローチの実装を以下に示します。
C++ // O(n*k) solution for finding maximum sum of // a subarray of size k #include using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) { // Initialize result int max_sum = INT_MIN; // Consider all blocks starting with i. for (int i = 0; i < n - k + 1; i++) { int current_sum = 0; for (int j = 0; j < k; j++) current_sum = current_sum + arr[i + j]; // Update result if required. max_sum = max(current_sum, max_sum); } return max_sum; } // Driver code int main() { int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 }; int k = 4; int n = sizeof(arr) / sizeof(arr[0]); cout << maxSum(arr, n, k); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)> C // O(n*k) solution for finding maximum sum of // a subarray of size k #include #include #include // Find maximum between two numbers. int max(int num1, int num2) { return (num1>番号2) ?番号 1 : 番号 2; } // サイズ k の部分配列の最大合計を返します。 int maxSum(int arr[], int n, int k) { // 結果を初期化 int max_sum = INT_MIN; // i で始まるすべてのブロックを考慮します。 for (int i = 0; i< n - k + 1; i++) { int current_sum = 0; for (int j = 0; j < k; j++) current_sum = current_sum + arr[i + j]; // Update result if required. max_sum = max(current_sum, max_sum); } return max_sum; } // Driver code int main() { int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 }; int k = 4; int n = sizeof(arr) / sizeof(arr[0]); printf('%d', maxSum(arr, n, k)); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)> ジャワ // Java code O(n*k) solution for finding maximum sum of // a subarray of size k class GFG { // Returns maximum sum in // a subarray of size k. static int maxSum(int arr[], int n, int k) { // Initialize result int max_sum = Integer.MIN_VALUE; // Consider all blocks starting with i. for (int i = 0; i < n - k + 1; i++) { int current_sum = 0; for (int j = 0; j < k; j++) current_sum = current_sum + arr[i + j]; // Update result if required. max_sum = Math.max(current_sum, max_sum); } return max_sum; } // Driver code public static void main(String[] args) { int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 }; int k = 4; int n = arr.length; System.out.println(maxSum(arr, n, k)); } } // This code is contributed by Aditya Kumar (adityakumar129)> Python3 # code import sys # O(n * k) solution for finding # maximum sum of a subarray of size k INT_MIN = -sys.maxsize - 1 # Returns maximum sum in a # subarray of size k. def maxSum(arr, n, k): # Initialize result max_sum = INT_MIN # Consider all blocks # starting with i. for i in range(n - k + 1): current_sum = 0 for j in range(k): current_sum = current_sum + arr[i + j] # Update result if required. max_sum = max(current_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 n = len(arr) print(maxSum(arr, n, k)) # This code is contributed by mits>
C# // C# code here O(n*k) solution for // finding maximum sum of a subarray // of size k using System; class GFG { // Returns maximum sum in a // subarray of size k. static int maxSum(int[] arr, int n, int k) { // Initialize result int max_sum = int.MinValue; // Consider all blocks starting // with i. for (int i = 0; i < n - k + 1; i++) { int current_sum = 0; for (int j = 0; j < k; j++) current_sum = current_sum + arr[i + j]; // Update result if required. max_sum = Math.Max(current_sum, max_sum); } return max_sum; } // Driver code public static void Main() { int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 }; int k = 4; int n = arr.Length; Console.WriteLine(maxSum(arr, n, k)); } } // This code is contributed by anuj_67.> JavaScript function maxSum(arr, n, k) { let max_sum = 0; // Loop from i to k for (let i = 0; i < k; i++) { max_sum += arr[i]; } let window_sum = max_sum; for (let i = k; i < n; i++) { window_sum = window_sum - arr[i - k] + arr[i]; max_sum = Math.max(max_sum, window_sum); } return max_sum; } // Driver code let arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]; let k = 4; let n = arr.length; console.log(maxSum(arr, n, k));> PHP // code ?>// サイズ k の部分配列の最大合計を見つけるための O(n*k) 解 // サイズ k の部分配列の最大合計を返します。 function maxSum($arr, $n, $k) { // 結果を初期化 $max_sum = PHP_INT_MIN ; // i で始まるすべてのブロックを // 考慮します。 for ( $i = 0; $i< $n - $k + 1; $i++) { $current_sum = 0; for ( $j = 0; $j < $k; $j++) $current_sum = $current_sum + $arr[$i + $j]; // Update result if required. $max_sum = max($current_sum, $max_sum ); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67. ?>>> 出力
24>
時間計算量: 2 つのネストされたループが含まれるため、O(k*n)。
補助スペース: ○(1)
スライディング ウィンドウ手法を適用すると、次のようになります。
- 線形ループを使用して n 項のうち最初の k 要素の合計を計算し、その合計を変数に格納します ウィンドウサム 。
- 次に、配列を最後に到達するまで線形に走査し、同時に最大合計を追跡します。
- k 要素のブロックの現在の合計を取得するには、前のブロックから最初の要素を減算し、現在のブロックの最後の要素を加算するだけです。
以下の図は、ウィンドウが配列上でどのようにスライドするかを明確に示しています。
配列を考えてみましょう 到着[] = {5, 2, -1, 0, 3} および次の値 k = 3 そして n = 5
これは、インデックス 0 から開始して初期ウィンドウ合計を計算した初期段階です。この段階では、ウィンドウの合計は 6 です。ここで、maximum_sum を current_window、つまり 6 に設定します。
ここで、ウィンドウを単位インデックスごとにスライドさせます。したがって、今度はウィンドウから 5 を破棄し、ウィンドウに 0 を追加します。したがって、5 を減算し、それに 0 を加算することで、新しいウィンドウの合計を取得します。したがって、ウィンドウの合計は 1 になります。次に、このウィンドウの合計を Maximum_sum と比較します。小さいので、maximum_sum は変更しません。
同様に、ここでもう一度、ウィンドウをユニット インデックスだけスライドさせて、新しいウィンドウの合計が 2 になるように取得します。再度、この現在のウィンドウの合計が今までの maximum_sum より大きいかどうかを確認します。もう一度言いますが、小さいので、maximum_sum は変更しません。
したがって、上記の配列では、maximum_sum は 6 になります。
上記のアプローチのコードは次のとおりです。
C++ // O(n) solution for finding maximum sum of // a subarray of size k #include using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) { // n must be greater if (n <= k) { cout << 'Invalid'; return -1; } // Compute sum of first window of size k int max_sum = 0; for (int i = 0; i < k; i++) max_sum += arr[i]; // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window. int window_sum = max_sum; for (int i = k; i < n; i++) { window_sum += arr[i] - arr[i - k]; max_sum = max(max_sum, window_sum); } return max_sum; } // Driver code int main() { int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 }; int k = 4; int n = sizeof(arr) / sizeof(arr[0]); cout << maxSum(arr, n, k); return 0; }> ジャワ // Java code for // O(n) solution for finding // maximum sum of a subarray // of size k class GFG { // Returns maximum sum in // a subarray of size k. static int maxSum(int arr[], int n, int k) { // n must be greater if (n <= k) { System.out.println('Invalid'); return -1; } // Compute sum of first window of size k int max_sum = 0; for (int i = 0; i < k; i++) max_sum += arr[i]; // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window. int window_sum = max_sum; for (int i = k; i < n; i++) { window_sum += arr[i] - arr[i - k]; max_sum = Math.max(max_sum, window_sum); } return max_sum; } // Driver code public static void main(String[] args) { int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 }; int k = 4; int n = arr.length; System.out.println(maxSum(arr, n, k)); } } // This code is contributed // by prerna saini.> Python3 # O(n) solution for finding # maximum sum of a subarray of size k def maxSum(arr, k): # length of the array n = len(arr) # n must be greater than k if n <= k: print('Invalid') return -1 # Compute sum of first window of size k window_sum = sum(arr[:k]) # first sum available max_sum = window_sum # Compute the sums of remaining windows by # removing first element of previous # window and adding last element of # the current window. for i in range(n - k): window_sum = window_sum - arr[i] + arr[i + k] max_sum = max(window_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 print(maxSum(arr, k)) # This code is contributed by Kyle McClay> C# // C# code for O(n) solution for finding // maximum sum of a subarray of size k using System; class GFG { // Returns maximum sum in // a subarray of size k. static int maxSum(int[] arr, int n, int k) { // n must be greater if (n <= k) { Console.WriteLine('Invalid'); return -1; } // Compute sum of first window of size k int max_sum = 0; for (int i = 0; i < k; i++) max_sum += arr[i]; // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window. int window_sum = max_sum; for (int i = k; i < n; i++) { window_sum += arr[i] - arr[i - k]; max_sum = Math.Max(max_sum, window_sum); } return max_sum; } // Driver code public static void Main() { int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 }; int k = 4; int n = arr.Length; Console.WriteLine(maxSum(arr, n, k)); } } // This code is contributed by anuj_67.> JavaScript >>
PHP // O(n) solution for finding maximum sum of // a subarray of size k // Returns maximum sum in a // subarray of size k. function maxSum( $arr, $n, $k) { // n must be greater if ($n <= $k) { echo 'Invalid'; return -1; } // Compute sum of first // window of size k $max_sum = 0; for($i = 0; $i < $k; $i++) $max_sum += $arr[$i]; // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window. $window_sum = $max_sum; for ($i = $k; $i < $n; $i++) { $window_sum += $arr[$i] - $arr[$i - $k]; $max_sum = max($max_sum, $window_sum); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67 ?>>> 出力
24>
時間計算量: O(n)、ここで n 入力配列のサイズです 到着[] 。
補助スペース: ○(1)
UDPプロトコル
2. 合計が指定された値より大きい最小の部分配列:
配列が与えられた場合 到着[] 整数と数値の バツ の場合、タスクは、指定された値よりも大きい合計を持つ最小の部分配列を見つけることです。
アプローチ：
この問題は、スライディング ウィンドウ テクニックを使用し、ウィンドウの開始と終了をマークする start と end という 2 つのポインターを維持することで解決できます。ウィンドウの合計が X 以下になるまで終了ポインタをインクリメントし続けることができます。ウィンドウの合計が X より大きくなると、ウィンドウの長さを記録し、ウィンドウの合計になるまで開始ポインタを移動し始めます。ここで、合計が X 以下になったら、再び終了ポインタのインクリメントを開始します。配列の最後に到達するまで、開始ポインタと終了ポインタを移動し続けます。
3. 非負の整数の配列内で指定された合計を持つ部分配列を検索します。
配列が与えられた場合 到着[] 負でない整数と整数の 和 、指定された値に加算する部分配列を見つけます。 和 。
アプローチ：
部分配列内のすべての要素が正であることがわかっているので、考え方は簡単です。そのため、部分配列の合計が 与えられた合計 その場合、現在の部分配列に要素を追加しても、指定された合計と等しくなる可能性はありません。したがって、アイデアは、同様のアプローチを使用することです スライドウィンドウ 。
- 空の部分配列から始めます。
- 合計が以下になるまで要素を部分配列に追加します バツ (与えられた合計) 。
- 合計がより大きい場合 バツ から要素を削除します。 始める 現在のサブ配列の。
4. 文字列自体のすべての文字を含む最小のウィンドウ:
アプローチ：
基本的に文字のウィンドウは 2 つのポインタを使用して維持されます。 始める そして 終わり 。これら 始める そして 終わり ポインタを使用して、ウィンドウのサイズをそれぞれ縮小および拡大できます。ウィンドウに指定された文字列のすべての文字が含まれる場合は常に、ウィンドウは左側から縮小されて余分な文字が削除され、その長さがこれまでに見つかった最小のウィンドウと比較されます。
現在のウィンドウでこれ以上文字を削除できない場合は、次のコマンドを使用してウィンドウのサイズを拡大し始めます。 終わり 文字列内に存在するすべての個別の文字がウィンドウ内に表示されるまで。最後に、各ウィンドウの最小サイズを見つけます。
スライディング ウィンドウ手法に関する練習問題:
問題 | 問題のリンク |
|---|---|
指定された合計を持つ部分配列を検索します | 解決する |
スライディング ウィンドウの最大値 (サイズ K のすべての部分配列の最大値) | 解決する |
合計 K を持つ最長の部分配列 | 解決する |
サイズ k の部分配列の最大 (または最小) 合計を求めます。 | 解決する |
他の文字列のすべての文字を含む文字列内の最小ウィンドウ | 解決する |
繰り返し文字を含まない最長の部分文字列の長さ | 解決する |
サイズ k のすべてのウィンドウ内の最初の負の整数 | 解決する |
サイズ k のすべてのウィンドウ内の個別の要素を数える | 解決する |
文字列自体のすべての文字を含む最小のウィンドウ | 解決する レル対セントス |
少なくとも k 個の数値を持つ最大の合計部分配列 | 解決する |
関連記事：
- R スライディング ウィンドウ技術に関する最近の記事
- スライディング ウィンドウに関する練習問題
- DSA セルフペース – DSA で最も使用され信頼されているコース