138.Subarray Sum

1.Description(Easy)

Given an integer array, find a subarray where the sum of numbers iszero. Your code should return the index of the first number and the index of the last number.

Notice

There is at least one subarray that it's sum equals to zero.

Example

Given[-3, 1, 2, -3, 4], return[0, 2]or[1, 3].

2.Code

记录每一个位置的sum，存入HashMap中，如果某一个sum已经出现过，那么说明中间的subarray的sum为0. 时间复杂度O(n)，空间复杂度O(n)

 public ArrayList<Integer> subarraySum(int[] nums) {
        ArrayList<Integer> result=new ArrayList<Integer>();
        if(nums==null ||nums.length==0){
            return result;
        }
        //key:sum  value:index
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        map.put(0, -1);

        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum=sum+nums[i];
            if(map.containsKey(sum)){
                int start=map.get(sum)+1;
                int end=i;
                result.add(start);
                result.add(end);
                return result;
            }else{
                map.put(sum,i);
            }
        }
        return result;
    }