Cho mảng số và số mục tiêu, tìm tất cả mảng con liên tiếp có tổng bằng số mục tiêu.
Ví dụ:
const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27]; const sum = 40; console.log(requiredSum(arr, sum));
Kết quả:
[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]
Thuật toán cửa sổ trượt (Sliding Window) - O(n)
Tạo cửa sổ (mảng con) mở rộng/thu hẹp để đạt tổng mục tiêu. Bắt đầu từ trái, trượt sang phải.
Ví dụ
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 là đầu/cuối cửa sổ. Mở rộng nếu tổng nhỏ, thu hẹp nếu lớn, bằng thì lưu và trượt cửa sổ.
Kết quả
Đầu ra console:
[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]