Mảng con nhị phân có tổng mong muốn trong JavaScript

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một mảng nhị phân arr làm đối số thứ nhất, và một số target làm đối số thứ hai. Hàm phải đếm số mảng con tồn tại trong arr có tổng phần tử bằng target và trả về số lượng này.

Ví dụ, nếu đầu vào là:

Đầu vào

const arr = [1, 0, 1, 0, 1];
const target = 2;

Đầu ra

const output = 4;

Giải thích

Các mảng con mong muốn là: [1,0,1], [1,0,1,0], [0,1,0,1], [1,0,1].

Ví dụ

const arr = [1, 0, 1, 0, 1];
const target = 2;
const countSubarrays = (arr = [], target = 1) => {
  const map = {};
  let sum = 0;
  let count = 0;
  for (const num of arr) {
    map[sum] = (map[sum] || 0) + 1;
    sum += num;
    count += map[sum - target] || 0;
  }
  return count;
};
console.log(countSubarrays(arr, target));

Kết quả

4