合計が数値に等しいすべてのサブ配列を検索しますか？ JavaScript（スライディングウィンドウアルゴリズム）

数字の配列と数字が与えられます。私たちの仕事は、2番目の引数として指定された数に加算されるすべてのサブ配列の配列を返す関数を作成することです。

例-

const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27];
const sum = 40;
console.log(requiredSum(arr, sum));

次の配列を出力する必要があります-

[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]

これらの3つのサブアレイのそれぞれが合計40になるためです。

スライディングウィンドウアルゴリズム（線形時間）

このアルゴリズムは主に、特定の条件を満たす文字列内の配列/サブ文字列内のサブ配列を検索する必要がある場合に使用されます。そして、この問題は、スライディングウィンドウアルゴリズムの完璧な候補です。

スライディングウィンドウアルゴリズムは、その名前が示すとおりです。元の配列のサブ配列にすぎないウィンドウを作成します。このウィンドウは、増減することで安定性を獲得しようとします。

安定性とは、問題で指定された条件を意味します（ここで特定の数を合計するなど）。安定したら、ウィンドウを記録してスライドを続けます。一般に、問題の90％で、ウィンドウを左から開始し、配列/文字列の最後に到達するまでスライドし続けます。

スライディングウィンドウアルゴリズムに慣れるためのコードを見てみましょう。

例

const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27];
const sum = 40;
const findSub = (arr, sum) => {
   const required = [];
   for(let start = 0, end = 0, s = 0; end <= arr.length || s > sum ; ){
      if(s < sum){
         s += arr[end];
         end++;
      }else if(s > sum){
         s -= arr[start];
         start++;
      }else{
         required.push(arr.slice(start, end));
         s -= arr[start];
         s += arr[end];
         start++;
         end++;
      };
   };
   return required;
};
console.log(findSub(arr, sum));

開始変数と終了変数は、さまざまなポイントでのウィンドウの開始位置と終了位置を示します。

最初は両方とも0から開始し、必要な合計が指定された合計よりも小さい場合はウィンドウのサイズを増やし、大きい場合はウィンドウサイズを減らし、いずれかの時点で両方の合計が等しい場合は、そのサブ配列を必要な配列にプッシュしました。そして、ウィンドウを単位距離だけ右に移動しました。

出力

コンソールでのこのコードの出力は-

[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]