合計Kを使用したJavaScriptの合計サブ配列

最初の引数として数値の配列を取り、2番目の引数として単一の数値を受け取るJavaScript関数を作成する必要があります。関数は、合計が2番目の引数で指定された数に等しい連続サブアレイの総数を見つけて返す必要があります。

配列内のすべての数値が正の数であることが保証されています。

例-

入力が-

const arr = [1, 1, 1];
const sum = 2;

この配列には合計が2になるサブ配列が正確に2つあるため、出力は2になります。

2ポインターアプローチを使用するスライディングウィンドウアルゴリズムを使用して、目的のウィンドウ（必要な合計を持つサブアレイ）を見つけ、それらの数をカウントします。

例

const arr = [1, 2, 3, 4, 5];
const sum = 5;
// two pointer approach to find one matching subarray
const findOne = (arr, target, start = 0) => {
   let left = start, right = start, sum = 0;
   while(right < arr.length){
      sum += arr[right];
      if(sum === target){
         return true;
      }
      else if(sum < target){
         right++;
      }else{
         left++;
         sum -= left;
         if(left > right){
            right = left;
         };
      };
   };
   return false;
};
// iterating over the array to find all pair count const findAll = (arr = [], target) => {
   let count = 0;
   for(let i = 0; i < arr.length; i++){
      count += findOne(arr, target, i);
   };
   return count;
};
console.log(findAll(arr, sum));
console.log(findAll([1, 1, 1], 2));

出力

そして、コンソールの出力は-

2
2