Subarray Sum

Description

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.

 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].

Link

Lintcode_ladder

Method

1. Use running sum to find any point has the same running sum
2. x

Example

1. 1

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
        if (nums.empty()) {
            return {};
        }
        int n = nums.size();
        int sum = 0;
        vector<int> result;
        unordered_map<int, int> dict;
        dict[0] = -1;
        // when two running sum is the same, the subarray must be between these two 
        // array : 1 1 -3 2 -3 4
        // runsum: 1 2 -1 1 -2 2
        // so, the subarray must be 1,1 and 2,2
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            if (dict.find(sum) != dict.end()) {
                result.push_back(dict[sum]+1);
                result.push_back(i);
                return result;
            }
            dict[sum] = i;
        }
        return result;
    }
};

Similar problems

x

Tags

x