javascript - 找出数组中具有给定总和的子数组的数量

Question

找到一个数组中子数组的数量，它具有给定的总和 - 这是我的尝试，但不能正常工作

function getSubArrayCount(arr, sum) {

for (var i = 0; i < arr.length; i++) {
        var str = [];
        var csum= 0;
        var output = 0;

for (var j = i; j < arr.length; j++) {        
        csum+= arr[j];
        str.push(arr[j]);
        if (csum== sum) {       
              return(str[i]);     
             }
         }
     }
}

console.log(getSubArrayCount([1,2,3,2,1,8,-3],5))

Answer 1

还有一种线性(取决于 map 实现)时间复杂度需要 O(n) 内存的方法。

将累积和与计数器一起存储在 map 中(已经达到某个累积和的次数)。在每一步检查当前的累计和形式是否需要与存储的相加。

我不熟悉 JS 但似乎这段代码有效

function getSubArrayCount(arr, sum) {
  let map = new Map();
  var cumsum = 0; var cnt = 0;
  map.set(0, 1);
  for (var i = 0; i < arr.length; i++) {
  	cumsum += arr[i];
  	if (map.has(cumsum - sum))
  	   cnt += map.get(cumsum - sum);
  	if (map.has(cumsum))
  	   map.set(cumsum, map.get(cumsum) + 1);
  	else  
           map.set(cumsum, 1);
  }
  return cnt;
}

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