Javascript - сумма подмассива равна K

Question

Я просто смотрю на некоторые вопросы интервью и наткнулся на этого парня

Given an array of integers and an integer k, 
you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:
Input:nums = [1,1,1], k = 2
Output: 2

Я знаю, что могу oop закончить и сделать это более многословно, но мне интересно, Я могу использовать reduce.

У меня есть следующее, что мне не удается передать следующие аргументы:

subarraySum([-1,-1,1], 0)

const subarraySum = (nums, k) => {
    let answer = 0;
    nums.reduce((acc, val) => {          
        if(acc + val === k) {
            answer++;
            return val;
        }
        if(val === k) {
            answer++
            return val
        }
        return acc + val;
    }, 0)

    return answer;
};

Answer 1

Да, использование reduce здесь довольно удобно для ответа на вопрос в линейном времени, поскольку оно позволяет обновлять и пересматривать накопленные значения:

const subarraySum = (nums, k) =>
  nums.reduce(([map, sum, answer], val) => {     
    const newSum = sum + val;
    answer += newSum == k;
    answer += map[newSum - k] || 0;
    map[newSum] = (map[newSum] || 0) + 1;
    return [map, newSum, answer];
  }, [{}, 0, 0])[2];

console.log(subarraySum([-1,-1,1], 0));
console.log(subarraySum([1,-1,1,-1], 0));

Answer 2

Снижение было бы излишним. Кроме того, непроизводительные затраты на вызов своего обратного вызова для каждого элемента сделают ваш алгоритм менее эффективным.

A для l oop - лучший способ для go. Вы можете найти возможное не наивное решение ниже:

var arr = [1, 2, 3, 4, 5];
    var map = [];
    var counter = 0;
    var k = 5;

    function updateMap(newValue) {
      map.push(0); // Placeholder for the new value;
      for (var i = 0; i < map.length; i++) {
        map[i] += newValue; // Increment the subcounts.
        if (map[i] === k) {
          counter++; // Found a match
          map = map.splice(i, 1); // Remove the matching subcount so you don't update nor check it again.
        }
      }
    }

    for(var i = 0; i < arr.length; i++){
      updateMap(arr[i]);
    }

    console.log("Results: " + counter);