题目-子数组和为零
给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置。
示例
给出[-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]);
为了在一个循环里面写完,牺牲了一些空间复杂度。
请你自动动手试一下:在线编程环境