找出数组和为零的子数组

题目-子数组和为零 #

给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置。

示例 #

给出[-3, 1, 2, -3, 4]，返回[0, 2] 或者 [1, 3].

分析 #

看清楚题目，这里的子数组是一串连续的子数组。只要找到起始位置和结束为止就可以了。

依次求数组的前缀和，同时执行如下操作：

假定当前位置是i，查找i之前位置的前缀和，是否存在j位置，使得，j位置的前缀和 等于 i位置的前缀和。

若有，则j 到 i 之间的区间数的和为0.

直到遍历完整个数组。

时间复杂度O(n)，空间复杂度O(n).

Just Try #

请你自动动手试一下：在线编程环境

想想有没有其他思路？

想想时间和空间复杂度，能否优化一下

真的做不到么？

let you think， think makes you happy!

参考答案 #

function algorithm(arr){
  let sum = 0, map = {}, res=[];
  arr.forEach((k,i)=>{
    sum += k;
    if(map[sum]){
      map[sum].push(i)
    }
    else{
      map[sum] = [i+1];
    }
    if(sum !=0 && map[sum].length>1){
      // 个数大于1，是一个子串
      res.push(map[sum])
    }
    if(sum == 0){
      // 和等于0，记录下位置
      res.push([0, i])
    }
  }
             )
  return JSON.stringify(res);
}
function main(param) {
  console.show("参数：" + param, "结果：" + algorithm(param))
  console.show(testPerformance(algorithm, param))
}
main([-3, 1, 2, -3, 4, -3, 2]);

为了在一个循环里面写完，牺牲了一些空间复杂度。

请你自动动手试一下：在线编程环境