第七章 数组

[-3,1,2,-3,4]

找到一个字数组，让他们的和=0.

TAG : PREFIX_SUM + HASH

code

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> ret;
        if(nums.size() == 0)
        {
            return ret;
        }

        map<int, int> sum_map;
        sum_map[0] = 0;
        int sum = 0;
        for(int i = 0; i<nums.size(); i++)
        {
            sum += nums[i];
            if(sum_map.find(sum) != sum_map.end())
            {
                ret.push_back(sum_map[sum]);
                ret.push_back(i);
                return ret;
            }
            sum_map[sum] = i+1;
        }
        return ret;
    }
};