JavaScript รวม subarrays กับ Sum K

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

รับประกันได้ว่าตัวเลขทั้งหมดในอาร์เรย์เป็นจำนวนบวก

ตัวอย่างเช่น −

หากอินพุตเป็น −

const arr = [1, 1, 1];
const sum = 2;

ผลลัพธ์ควรเป็น 2 เพราะมีอาร์เรย์ย่อยสองชุดในอาร์เรย์นี้ที่รวมเป็น 2

เราจะใช้อัลกอริธึมหน้าต่างบานเลื่อนที่ใช้วิธีการแบบสองพอยน์เตอร์เพื่อค้นหาหน้าต่างที่ต้องการ (แถบย่อยที่มีผลรวมที่จำเป็น) และนับจำนวนหน้าต่างนั้น

ตัวอย่าง

const arr = [1, 2, 3, 4, 5];
const sum = 5;
// two pointer approach to find one matching 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 -= left;
         if(left > right){
            right = left;
         };
      };
   };
   return false;
};
// iterating over the array to find all pair count 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