前端学堂
学有所用

找出数组和为零的子数组

题目-子数组和为零

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

示例

给出[-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]);

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

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

赞(2) 打赏
未经允许不得转载:前端学堂 » 找出数组和为零的子数组

评论 抢沙发

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏