Tìm tất cả các phân thức có tổng bằng số? JavaScript (Thuật toán cửa sổ trượt)

Chúng tôi được cung cấp một mảng số và một số; Công việc của chúng ta là viết một hàm trả về một mảng của tất cả các mảng con cộng lại thành số được cung cấp dưới dạng đối số thứ hai.

Ví dụ -

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

Sẽ xuất ra mảng sau -

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

Bởi vì mỗi mảng trong số 3 mảng con này cộng lại lên đến 40.

Thuật toán cửa sổ trượt (Thời gian tuyến tính)

Thuật toán này chủ yếu được sử dụng khi chúng ta được yêu cầu tìm các mảng con trong một mảng / chuỗi con trong một chuỗi thỏa mãn các tiêu chí nhất định. Và chính vấn đề này là một ứng cử viên hoàn hảo cho thuật toán cửa sổ trượt.

Thuật toán cửa sổ trượt đúng như tên gọi của nó, chúng tôi tạo ra một cửa sổ chẳng qua là một mảng con của mảng ban đầu. Cửa sổ này cố gắng đạt được sự ổn định bằng cách tăng thứ tự.

Theo tính ổn định, chúng tôi muốn nói đến điều kiện được chỉ định trong bài toán (như cộng đến một số cụ thể ở đây). Khi nó trở nên ổn định, chúng tôi ghi lại cửa sổ và tiếp tục trượt nó. Nói chung, trong 90% các vấn đề, chúng tôi bắt đầu cửa sổ từ bên trái và tiếp tục trượt nó cho đến khi nó chạm đến cuối mảng / chuỗi.

Hãy xem mã để làm cho chúng ta quen thuộc hơn với thuật toán Trượt Windows.

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));

Các biến bắt đầu và kết thúc biểu thị vị trí bắt đầu và kết thúc của cửa sổ tại các điểm khác nhau.

Ban đầu cả hai đều bắt đầu từ 0, sau đó chúng tôi tăng kích thước của cửa sổ nếu tổng bắt buộc nhỏ hơn tổng đã cho, giảm kích thước cửa sổ nếu lớn hơn và nếu tại bất kỳ thời điểm nào cả hai đều là tổng, chúng tôi đẩy mảng con đó vào mảng bắt buộc. Và di chuyển cửa sổ sang phải theo đơn vị khoảng cách.

Đầu ra

Đầu ra của mã này trong bảng điều khiển sẽ là -

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