スライディングウィンドウ技術🔥

ねえ好奇心の人々👋! これまでに、問題を解決するだけでなく、効率的に解決アルゴリズムを書いた後に感じたことがありますか?このブログでは、我々はより頻繁にその感覚を得るのを助けるだろうアルゴリズムについて学びます!Sliding Window Technique(SWT)—私はこのアルゴリズムを、O(n←)からO(n)までの解決策(一般的に配列のようなシーケンシャルで反復可能なデータ構造を扱う問題に対して)の時間複雑性を改善するのを助けるものとして理解しています.

SWTとは

ほとんどの定義によると、SWTはいくつかのブルートフォース(ほとんどO(N))アルゴリズムを線形(O(N))アルゴリズムに変換する方法です.

便利ですか。

インタビューにおいて、O(n -ξ)からo(n)までのアルゴリズムを改善することは、大いに😅).

ハウツーとスタイル

方法を理解するには、まず問題を見てみましょう.まず、ブルートフォースの解決策を考え、SWTを適用して改良します.その前に、私たちがSWTをどのように適用するかについての基本的な考えを与えましょう.
配列を持っていて、配列の中で最大の要素を見つけたいとしましょう.解決策は、すべての要素を見て、最大の要素を追跡することです.SWTウェイに入れるには、以下のようになります.👇

今、あなたはそれを推測した可能性があります、ウィンドウのスライド(クリックしたか?💡) 左から右まで、それが我々が見た最大の要素であるならば、我々はValue Checkを見ます、そして、ウインドウが配列の終わりに達するまで、これは続きます.ウィンドウは、我々が扱っている問題に応じて任意のサイズであるかもしれません.ウィンドウのサイズを固定または動的にすることができます.

問題

nの正整数の配列が与えられた場合、

ブルートフォースアプローチ

私の心に来る最初のソリューションは、3つの連続した要素のすべての可能なサブ配列を見つけるために、その合計を見つけて、最大の1つを追跡することです.このために2つのネストしたループを必要とします.このアルゴリズムをコードで見ましょう.

let arr = [1, 3, 5, 6, 2, 7, 8];
let maxSum = 0;  //to keep track of maximum sum.

for (let i = 0; i < arr.length - 3 + 1; i++){
  //Initializing sum
  let sum = 0;
  //Adding 3 elements starting from i
  for (let j = 0; j < 3; j++){
    sum = sum + arr[i + j];
  }
  //Storing the maximum sum
  maxSum = Math.max(sum,maxSum);
}

console.log(maxSum);

このアルゴリズムの時間の複雑さはo(n * 3)であり、3の代わりにより大きな要素の集合であればより悪くなる可能性がある.

SWTアプローチ

さて、SWTアプローチの仕組みを見てみましょう.

今私たちがしたいサイズ3のウィンドウを持って、その合計のカウントを維持し、最大の合計を追跡するように右にスライドします.窓が1つの要素を右に動かすならば、どうなるかを視覚化しましょう.実際にしているのは、4番目の要素を合計に追加し、1番目の要素を差し引いて、ウィンドウが配列の最後に達するまで同じことを繰り返すことです.コードでどのように見えるか見てみましょう.

let arr = [1, 3, 5, 6, 2, 7, 8];
let maxSum = 0;  //to keep track of maximum sum.
let sumOfWindow = 0; //to keep track of sum of the window.
let windowSize = 0;

for (let i = 0; i < arr.length + 1; i++){
  if(windowSize == 3){
    console.log('current windows sum is');
    console.log(sumOfWindow);
    //storing the maximum sum
    maxSum = Math.max(maxSum, sumOfWindow);
    //deleting the end element of the window
    sumOfWindow = sumOfWindow - arr[i - 3];
    windowSize--;
  }

   //adding elements to the window.
  sumOfWindow = sumOfWindow + arr[i];
  windowSize++;

}

console.log("The maximum sum is: " + maxSum);

Voila!それは単一のループにあります.アヘン.To use fewer loops, use more brain AAAAA NDおそらくコードのいくつかのより多くの行.
あそこにある.Sliding Window Technique!

いつ使用するか。

私は一般的に、配列や文字列のようなiterableなデータ構造の連続した要素と関係がある問題を見ているときに使用します.
SWTについて知っているので、this problem in hackerrank?を試してみてください.念頭に置いて、ウィンドウのサイズを動的にすることができます、それは常に3つのような固定番号である必要はありません.
あなたがこのブログが好きであるならば、consider buying me a coffee😊またはsupport me in patreon .
このシリーズで他のブログをチェックしてください.👇