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

Tổng phạm vi

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

Mô tả vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào mảng số nguyên arr làm đối số đầu tiên, và hai số upper và lower làm đối số thứ hai và thứ ba.

Hàm phải trả về số lượng tổng phạm vi nằm trong khoảng [lower, upper] (bao gồm cả hai đầu).

Ví dụ, nếu đầu vào là:

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

Thì đầu ra nên là:

const output = 3;

Ví dụ minh họa

Mã thực hiện (sử dụng mảng tiền tố đã sắp xếp + tìm kiếm nhị phân):

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

Kết quả trong console sẽ là:

3