Subarray Sum

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

暴力解法

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    public List<Integer> subarraySum(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0){
            return result;
        }
        
        int sum = 0;
        
        // 从每一个数开始找subarray
        for (int i = 0; i < nums.length; i++){
            
            // 单个的subarray和为0 return
            if (nums[i] == 0){
                result.add(i);
                result.add(i);
                return result;
            }
            
            sum = nums[i];
            
            // 找下一个连续的数来组成subarray, 叠加找到和为零return
            for (int j = i + 1; j < nums.length; j++){
                sum += nums[j];
                if (sum == 0){
                    result.add(i);
                    result.add(j);
                    return result;
                }
            }
        }
        return result;
    }
}

DP解法

记录index 0到array中每一个end index之和，记录到hashmap中，因为subarray一定连续的性质，如果在找到一样的和，相当于之前的end index到当前end index之间的这一段subarray的和是0；

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    public List<Integer> subarraySum(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0){
            return result;
        }
        
        // record accumulated sum from 0 to i
        int sum = 0;
        
        // Key: sum from 0 to end index, value of end index
        Map<Integer, Integer> map = new HashMap<>();
        
        map.put(0, -1); // 0到i idnex之和为0的情况，-1 + 1 = 0
        
        
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            
            
            if (!map.containsKey(sum)){
                map.put(sum, i);
            } 
            
            // 之前还有这个sum也就是说从现在的sum减去之前的sum等于0
            // 也就是说之前的end到现在end加起来等于0
            // eg. 1 2 -1 -1 
            //     1 -> 1  and  1, 2, -1, -1 -> 1  => 2, -1, -1 -> 0
            else {
                result.add(map.get(sum) + 1);  
                result.add(i);
                return result;
            }
        }
        
        return result;
    }
}