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.

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

http://www.lintcode.com/en/problem/subarray-sum/

Discussion

暴力法O(n^2)就不说了。怎么样遍历一次就找出这个subarray呢？遍历到i还可以额外得到的信息就是从0到i的累计sum，这是一个非常重要的方法，常常碰到，因为它提供了额外的信息。我们用sum[i]表示从0到i的sum，如果sum[j]==sum[i] (j>i)，那说明从i+1到j的和是零啊！！

那么问题来了，怎么样判断sum[j]是否在之前的sum[i]中出现过呢？判断一个数在一系列数中是否存在，这个问题问的好熟悉哦，hash啊！！

class Solution {
public:
    /**
     * @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
     */
    vector<int> subarraySum(vector<int> nums){
        // write your code here
        vector<int> result;
        int n = nums.size();
        if(n==0) return result;
        unordered_map<int, int> map;
        int acSum = 0;
        for(int i=0; i<n; i++) {
            if(nums[i] == 0) {
                result.push_back(i);
                result.push_back(i);
                break;
            }
            acSum += nums[i];
            if(acSum == 0) {
                result.push_back(0);
                result.push_back(i);
                break;
            }
            if(map.find(acSum) != map.end()) {
                result.push_back(map[acSum] +1);
                result.push_back(i);
                break;
            } else {
                map[acSum] = i;
            }
        }
        return result;
    }
};

有两处细节，一是当前number为0，一是当前sum[i]为零，见code。 更简洁的写法如下：

vector<int> subarraySum(vector<int> nums){
        if(nums.empty()) return nums;
        unordered_map<int, int> map;
        int accu = 0;
        map[0] = -1;
        for(int i=0; i<nums.size(); i++) {
            accu += nums[i];
            if(map.find(accu) != map.end()) {
                //return vector<int>({map[accu]+1, i});
                return {map[accu]+1, i};
            }
            map[accu] = i;
        }
        return {};
    }

暴力法也没有一次bug free，不信再试试？