lintcode | 138.子数组之和

题目

给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置 注意事项 There is at least one subarray that it’s sum equals to zero. 样例 给出 [-3, 1, 2, -3, 4]，返回[0, 2] 或者 [1, 3].

我的思路

数组从i开始往后加，加到和为0即可。 1. 两个循环。for(i=0;i < nums.length;i++)和for(j=i;j < nums.length;j++)，i循环记录相加的起始位置，j循环记录sum为0时的结束位置。 2. 注意nums为[0]的情况。

代码

// 时间复杂度: O(n*2) 总耗时：6488ms public ArrayList<Integer> subarraySum(int[] nums){ int i,j,sum; int first,last; int ret=0; ArrayList<Integer> retSet=new ArrayList<Integer>(); for(i=0;i<nums.length;i++) { sum=0; //sum=nums[i]; //测试未通过时代码：用i位置值初始化sum //for(j=i+1;j<nums.length;j++) //测试未通过时代码：j=i+1，j从i的下一位开始，然后sum+=nums[j] for(j=i;j<nums.length;j++) { sum+=nums[j]; if(sum==0) { ret++; first=i; last=j; retSet.add(first); retSet.add(last); break; } } if(ret!=0) break; } return retSet; }

注意

代码中注释了“测试未通过时代码“，j=i+1，忽略了nums只有一个元素的情况。并不需要返回全部的满足条件的[first,last]，题目中给出样例是：给出 [-3, 1, 2, -3, 4]，返回[0, 2] 或者 [1, 3]。因此只要返回一个就行。

---

思考

上述方法的时间复杂度：O(n*2)，能否优化？

优化思路

想要降低时间复杂度，直接想法是降低到O(n)，那该如何只进行一次for循环就能确定结果呢？ 使用HashMap，元素相加的和作为key，value为 位置索引 [0,i] 的集合。哈希表的形式为：HashMap< Integer , ArrayList< Object > >

代码

//使用HashMap：时间复杂度 O(n) 总耗时：5183ms public ArrayList<Integer> subarraySum(int[] nums){ ArrayList<Integer> reSet=new ArrayList<Integer>(); int i,sum=0; HashMap<Integer,ArrayList<Object>> hash=new HashMap<Integer,ArrayList<Object>>(); int[] indexs; ArrayList<Object> res; for(i=0;i<nums.length;i++) { sum+=nums[i]; indexs=new int[2]; indexs[0]=0; indexs[1]=i; if(sum==0) //有sum为0，即返回 { reSet.add(0); reSet.add(i); return reSet; } res=hash.get(sum); if(res==null) { res=new ArrayList<Object>(); hash.put(sum, res); } res.add(indexs); } int[] indexs1,indexs2; for(ArrayList<Object> value:hash.values()) { if(value.size()>1) { indexs1=(int[])value.get(0); indexs2=(int[])value.get(1); reSet.add(indexs1[1]+1); reSet.add(indexs2[1]); return reSet; } } return reSet; }

注意

没有 if(sum==0) 判断部分时，测试未通过： 输入数据为[1,-1]时，返回值 [ ]，期待返回 [0,1]。 有sum为0，即返回，无需做后面工作