เราได้รับอาร์เรย์ของตัวเลขและตัวเลข งานของเราคือการเขียนฟังก์ชันที่ส่งคืนอาร์เรย์ของอาร์เรย์ย่อยทั้งหมดที่รวมกันเป็นตัวเลขที่ให้ไว้เป็นอาร์กิวเมนต์ที่สอง
ตัวอย่างเช่น −
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
อัลกอริธึมหน้าต่างบานเลื่อน (เวลาเชิงเส้น)
อัลกอริทึมนี้ส่วนใหญ่จะใช้เมื่อเราจำเป็นต้องค้นหาอาร์เรย์ย่อยภายในอาร์เรย์ / สตริงย่อยภายในสตริงที่ตรงตามเกณฑ์บางอย่าง และปัญหานี้ก็เป็นตัวเลือกที่สมบูรณ์แบบสำหรับอัลกอริธึมหน้าต่างบานเลื่อน
อัลกอริธึมหน้าต่างบานเลื่อนเป็นเพียงชื่อของมันเท่านั้น เราสร้างหน้าต่างที่ไม่มีอะไรเลยนอกจากอาร์เรย์ย่อยของอาร์เรย์ดั้งเดิม หน้าต่างนี้พยายามที่จะเพิ่มความเสถียรโดยการเพิ่มลำดับ
โดยความเสถียร เราหมายถึงเงื่อนไขที่ระบุในปัญหา (เช่น บวกกับตัวเลขเฉพาะที่นี่) เมื่อมันเสถียรแล้ว เราจะบันทึกหน้าต่างและเลื่อนต่อไป โดยทั่วไปใน 90% ของปัญหา เราจะเริ่มหน้าต่างจากด้านซ้ายและเลื่อนไปเรื่อย ๆ จนกว่าหน้าต่างจะสิ้นสุดที่ส่วนท้ายของอาร์เรย์ / สตริง
มาดูโค้ดเพื่อทำให้ตัวเองคุ้นเคยกับอัลกอริทึมของ Slide Windows มากขึ้น
ตัวอย่าง
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)); ตัวแปรเริ่มต้นและสิ้นสุดแสดงถึงตำแหน่งเริ่มต้นและสิ้นสุดของหน้าต่างที่จุดต่างๆ
เริ่มแรกทั้งคู่เริ่มต้นที่ 0 จากนั้นเราเพิ่มขนาดของหน้าต่างหากผลรวมที่ต้องการน้อยกว่าผลรวมที่กำหนด ลดขนาดหน้าต่างถ้ามันมากกว่า และหาก ณ จุดใดทั้งที่เท่ากัน เราก็ผลักอาร์เรย์ย่อยนั้นเข้าไปในอาร์เรย์ที่ต้องการ และเลื่อนหน้าต่างไปทางขวาตามระยะทางของหน่วย
ผลลัพธ์
ผลลัพธ์ของรหัสนี้ในคอนโซลจะเป็น −
[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]
