Đếm các cặp có tổng phạm vi trong một giới hạn trong JavaScript

Tổng phạm vi

Phạm vi tổng phạm vi Tổng (i, j) được định nghĩa là tổng các phần tử trong một mảng giữa các chỉ số i và j (i ≤ j), bao gồm cả.

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript lấy một mảng Số nguyên, arr, làm đối số thứ nhất và hai số, trên và dưới là phần tử thứ hai và thứ ba.

Hàm của chúng tôi phải trả về số lượng các tổng của dải ô nằm giữa dải ô [trên, dưới], (cả hai đều bao gồm).

Ví dụ:nếu đầu vào của hàm là -

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

Sau đó, đầu ra phải là -

const output = 3;

Ví dụ

Mã cho điều này sẽ là -

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));

Đầu ra

Đầu ra trong bảng điều khiển sẽ là -

3