หาซับอาร์เรย์ทุกชุดที่ผลรวมเท่ากับตัวเลข? JavaScript (Sliding Window Algorithm)

เราได้รับอาร์เรย์ตัวเลขและตัวเลขหนึ่ง หน้าที่คือเขียนฟังก์ชันคืนอาร์เรย์ของซับอาร์เรย์ทั้งหมดที่บวกกันได้ตัวเลขที่สอง

เช่น

const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27];
const sum = 40;
console.log(requiredSum(arr, sum));

ควรคืนอาร์เรย์

[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]

เพราะแต่ละซับอาร์เรย์ 3 ชุดนี้บวกกันได้ 40

อัลกอริทึม Sliding Window (Linear Time)

อัลกอริทึมนี้ใช้เมื่อต้องหาซับอาร์เรย์ในอาร์เรย์ / ซับสตริงในสตริง ที่ตรงตามเกณฑ์ โจทย์นี้เหมาะอย่างยิ่ง

Sliding window คือการสร้างหน้าต่างซึ่งเป็นซับอาร์เรย์ของอาร์เรย์ต้นทาง หน้าต่างพยายามหาสมดุลโดยขยายหรือหด

สมดุลหมายถึงเงื่อนไขในโจทย์ (เช่น บวกได้ตัวเลขเฉพาะ) เมื่อสมดุลแล้ว บันทึกหน้าต่างและเลื่อนต่อ ปกติ 90% ของปัญหา เริ่มหน้าต่างจากซ้าย และเลื่อนจนขอบขวาถึงปลายอาร์เรย์/สตริง

ดูโค้ดเพื่อเข้าใจ Sliding Window ดีขึ้น

ตัวอย่าง

const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27];
const sum = 40;
const findSub = (arr, sum) => {
  const required = [];
  for(let start = 0, end = 0, s = 0; end <= arr.length || s > sum ; ){
    if(s < sum){
      s += arr[end];
      end++;
    }else if(s > sum){
      s -= arr[start];
      start++;
    }else{
      required.push(arr.slice(start, end));
      s -= arr[start];
      s += arr[end];
      start++;
      end++;
    };
  };
  return required;
};
console.log(findSub(arr, sum));

ตัวแปร start และ end บ่งบอกตำแหน่งเริ่มและจบของหน้าต่างในแต่ละจุด

เริ่มทั้งคู่ที่ 0 แล้วเพิ่มขนาดหน้าต่างถ้าผลรวมน้อยกว่าเป้าหมาย ลดขนาดถ้ามากกว่า และถ้าเท่ากัน push ซับอาร์เรย์เข้า required array และเลื่อนหน้าต่างไปขวาหน่วยเดียว

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็น

[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]