การหาจำนวนซับอาร์เรย์ที่ผลรวมเท่ากับ K ใน JavaScript

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลข (ทั้งหมดเป็นบวก) และค่าเป้าหมาย (target sum) จากนั้นคืนจำนวนซับอาร์เรย์ที่ต่อเนื่องกันซึ่งผลรวมเท่ากับค่าเป้าหมาย

ตัวอย่าง: หากอินพุตคือ arr = [1, 1, 1] และ sum = 2 ผลลัพธ์ควรเป็น 2 เนื่องจากมีซับอาร์เรย์ 2 ชุดที่ผลรวมได้ 2

เราจะใช้อัลกอริทึม Sliding Window (หน้าต่างเลื่อน) แบบ Two-pointer เพื่อหาช่วงที่ต้องการและนับจำนวน

ตัวอย่างโค้ด

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

// ฟังก์ชันช่วยหา subarray หนึ่งชุดจากตำแหน่งเริ่มต้น
const findOne = (arr, target, start = 0) => {
  let left = start, right = start, sum = 0;
  while (right < arr.length) {
    sum += arr[right];
    if (sum === target) {
      return true;
    } else if (sum < target) {
      right++;
    } else {
      left++;
      sum -= arr[left - 1]; // หมายเหตุ: โค้ดต้นฉบับมี bug ตรงนี้ (sum -= left) ควรเป็น sum -= arr[left-1]
      if (left > right) {
        right = left;
      }
    }
  }
  return false;
};

// วนลูปหาจำนวนคู่ทั้งหมด
const findAll = (arr = [], target) => {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    count += findOne(arr, target, i);
  }
  return count;
};

console.log(findAll(arr, sum));
console.log(findAll([1, 1, 1], 2));

ผลลัพธ์

ค่าที่แสดงในคอนโซลจะเป็นดังนี้:

2 2