查找数组中具有给定总和的子数组的数量

问题描述 投票:0回答:3

查找数组中具有给定总和的子数组的数量 - 这是我的尝试,但无法正常工作

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))
javascript algorithm
3个回答
2
投票

还存在需要O(n)存储器的线性(取决于映射实现)时间复杂度的方法。

将累积总和与计数器一起存储在地图中(已经满足一些累积总和的次数)。在每个步骤检查当前累积总和形式是否需要与存储的总和。

我不熟悉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

1
投票

子数组被定义为原始数组的连续块。如果这是您正在寻找的,下面的代码应该工作:

function getSubArrayCount(arr, sum) {
  var output = 0, csum = 0;
  for (var i = 0; i < arr.length; i++) {
    for (var j = i; j < arr.length; j++) {        
      csum+= arr[j];
      if (csum== sum) {       
        output++;     
      }
    }
    csum= 0;
  }
  
  return output;
}

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

0
投票

找到给定总和的子阵列(一般 - 不连续)的数量是NP难问题。所以我们需要计算每个2 ^长度子阵列的和。这项任务最难的部分是生成n-thararray - 我们可以做到

let sub= (a,n)=> a.filter((x,i)=> n&(1<<i))

上面代码背后的想法是:如果我们在二进制系统中查看n,例如n=1010011b我们可以在标志1/0上查看它,它指示我们采用哪种元素进行子阵列

 [ 1, 2, 3, 2, 1, 8,-3 ]    
   1  0  1  0  0  1  1      ->     [1,3,8,-3]

所以我们测试数字n的第i位来过滤掉第i个元素。转角情况:我假设如果sum = 0,那么我们也计算空数组。这是完整的解决方案

function getSubArrayCount(a,sum) {
  let r=0, sub= (a,n)=> a.filter((x,i)=> n&(1<<i));
  for(let i=0; i<2**a.length; i++) 
    sub(a,i).reduce((s,c)=>s+c,0)==sum ? r++ : 0;
  return r;
}


console.log('[1,2,3,2,1,8,-3] sum=5 => ', getSubArrayCount([1,2,3,2,1,8,-3],5) );
console.log('[1,2,3,4] sum=10       => ', getSubArrayCount([1,2,3,4],10) );
console.log('[1,2,3,-3] sum=3       => ', getSubArrayCount([1,2,3,-3],3) );

我假设子阵列可以复制。如果我们不允许子阵列重复,答案会更复杂。

热门问题
推荐问题
最新问题