Алгоритм с линейной сложностью

Ответ:

const findSumOfSubarray = (arr, k) => {
  let total = 0;
  let partSum = 0;

  const map = new Map();
  map.set(0, 1);

  for (let i = 0; i < arr.length; i++) {
    partSum += arr[i];

    // found a subarray that sum of this subarray equals k
    if (map.has(partSum - k)) {
      total += map.get(partSum - k);
    }

    // add new part sum to dictionary
    if (!map.has(partSum)) {
      map.set(partSum, 0);
    }
    map.set(partSum, map.get(partSum) + 1);
  }

  return total;
};

Объяснение:

Идея решения заключается в использовании частичных сумм массива.

Рассмотрим пример, arr = [1, 2, 3]. Будем считать частичные суммы для каждого элемента, т.е.

partSum(i) = arr[0] + arr[1] + … + arr[i]

Для нашего примера массив частичных сумм будет следующим:

[1, 1 + 2, 1 + 2 + 3] = [1, 3, 6]

Нам нужно найти подмассив с суммой элементов равным K, т.е. подмассив {i, j}, где i — начальный индекс подмассива, j — конечный, а сумма его элементов Sum(i,j) = K.

Что такое Sum(i, j)?

Sum(N) = arr[0] + arr[1] + arr[2] + … + arr[i] + arr[i + 1] + … + arr[j] + arr[j + 1] + … + arr[N]

Sum(i) = arr[0] + arr[1] + arr[2] + … + arr[i]

Sum(j) = arr[0] + arr[1] + arr[2] + … + arr[i] + arr[i + 1] + … + arr[j]

Sum(i, j) — это разница между Sum(j) и Sum(i), т.е. Sum(i, j) = Sum(j) — Sum(i)

В конечном итоге, нам нужно посчитать кол-во Sum(i, j), ктр равны K. Или кол-во пар, где Sum(j) — Sum(i) = K. Sum(i) = Sum(j) — K.

Код для проверки:

const findSumOfSubarray = (arr, k) => {
  let total = 0;
  let partSum = 0;

  const map = new Map();
  map.set(0, 1);

  for (let i = 0; i < arr.length; i++) {
    partSum += arr[i];

    // found a subarray that sum of this subarray equals k
    if (map.has(partSum - k)) {
      total += map.get(partSum - k);
    }

    // add new part sum to dictionary
    if (!map.has(partSum)) {
      map.set(partSum, 0);
    }
    map.set(partSum, map.get(partSum) + 1);
  }

  return total;
};

console.log(findSumOfSubarray([1, 2, 3], 3)); // 2
console.log(findSumOfSubarray([1, 2, 3], 4)); // 0
console.log(findSumOfSubarray([1, 2, 3], 5)); // 1

console.log(findSumOfSubarray([1, 1, 1], 2)); // 2