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;

    }

注意

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

---

思考

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

优化思路

1. 想要降低时间复杂度，直接想法是降低到O(n)，那该如何只进行一次for循环就能确定结果呢？
   
2. 使用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;           
    }

注意

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