Sum K가 있는 JavaScript 총 하위 배열

Numbers 배열을 첫 번째 인수로, 단일 숫자를 두 번째 인수로 취하는 JavaScript 함수를 작성해야 합니다. 함수는 합계가 두 번째 인수로 지정된 수와 동일한 연속 하위 배열의 총 수를 찾아서 반환해야 합니다.

배열의 모든 숫자가 양수임을 보장합니다.

예를 들어 -

입력이 -

const arr = [1, 1, 1];
const sum = 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