합계가 숫자와 같은 모든 부분배열을 찾으시겠습니까? JavaScript(슬라이딩 창 알고리즘)

우리는 숫자 배열과 숫자를 받습니다. 우리의 임무는 두 번째 인수로 제공된 숫자까지 합해지는 모든 하위 배열의 배열을 반환하는 함수를 작성하는 것입니다.

예를 들어 -

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%에서 우리는 창을 왼쪽에서 시작하여 배열/문자열의 끝에 도달할 때까지 계속 슬라이딩합니다.

Sliding Windows 알고리즘에 더 익숙해지도록 코드를 살펴보겠습니다.

예시

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 ] ]