การนับคู่ที่มีผลรวมช่วงในขีดจำกัดใน JavaScript

ช่วงผลรวม

ช่วง ผลรวม rangeSum(i, j) ถูกกำหนดเป็นผลรวมขององค์ประกอบในอาร์เรย์ระหว่างดัชนี iand j (i ≤ j) รวมอยู่ด้วย

ปัญหา

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่ใช้อาร์เรย์ของจำนวนเต็ม arr เป็นอาร์กิวเมนต์แรกและตัวเลขสองตัว บนและล่างเป็นองค์ประกอบที่สองและสาม

ฟังก์ชันของเราควรจะส่งคืนจำนวนช่วงผลรวมที่อยู่ระหว่างช่วง [บน ล่าง] (รวมทั้งสองอย่าง)

ตัวอย่างเช่น หากอินพุตของฟังก์ชันคือ −

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