JavaScript의 한도에서 범위 합계가 있는 쌍 계산

범위 합계

범위 합계 rangeSum(i, j)은 인덱스 i와 j(i ≤ j)(포함) 사이의 배열에 있는 요소의 합으로 정의됩니다.

문제

우리는 첫 번째 인수로 정수 배열 arr을, 두 번째와 세 번째 요소로 위쪽과 아래쪽 두 개의 숫자를 취하는 JavaScript 함수를 작성해야 합니다.

우리 함수는 [상한, 하한] 범위(둘 다 포함) 사이에 있는 범위 합계의 수를 반환해야 합니다.

예를 들어, 함수에 대한 입력이 -

const arr = [1, 4, 3];
const upper = 5;
const lower = 2;

그러면 출력은 다음과 같아야 합니다. -

const output = 3;

예시

이에 대한 코드는 -

const arr = [1, 4, 3];
const upper = 5;
const lower = 2;
const countRangeSum = (arr = [], lower, upper) => {
   const sums = [0];
   let res = 0;
   let last = 0;
   let firstge = value => {
      let l = 0, r = sums.length, m;
      do {
         m = Math.floor((r + l) / 2);
         sums[m] < value ? l = m : r = m;
      } while (r >= l + 2);
      while (r > 0 && sums[r - 1] >= value ) {
         r -= 1;
      }
      return r;
   };
   arr.forEach(num => {
      last += num;
      res += firstge(last - lower + 1) - firstge(last - upper);
      sums.splice(firstge(last), 0, last);
   });
   return res;
};
console.log(countRangeSum(arr, lower, upper));

출력

콘솔의 출력은 다음과 같습니다. -

3