Tổng số mảng con liên tiếp có tổng bằng K trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào một mảng các số làm đối số thứ nhất và một số đơn lẻ làm đối số thứ hai. Hàm sẽ tìm và trả về số lượng mảng con liên tiếp có tổng bằng số được chỉ định.

Điều kiện: Tất cả các số trong mảng đều là số dương.

Ví dụ:

Nếu đầu vào là:

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

Đầu ra sẽ là 2 vì có chính xác hai mảng con có tổng bằng 2.

Chúng ta sẽ sử dụng thuật toán cửa sổ trượt với kỹ thuật hai con trỏ để tìm các cửa sổ mong muốn (mảng con có tổng yêu cầu) và đếm số lượng của chúng.

Ví dụ

const arr = [1, 2, 3, 4, 5]; const sum = 5; 
// Tìm một mảng con khớp với hai con trỏ
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 -= arr[left - 1]; 
      if (left > right) right = left; 
    } 
  } 
  return false; 
}; 
// Duyệt qua mảng để đếm tất cả các cặp
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));

Kết quả

Kết quả hiển thị trong console sẽ là:

2 2