Subarray Sum

• Lintcode : 138 / Leetcode :
• Level : Easy

Problem

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.

Example
Example 1:

Input:  [-3, 1, 2, -3, 4]
Output: [0, 2] or [1, 3].
Explanation: return anyone that the sum is 0.
Example 2:

Input:  [-3, 1, -4, 2, -3, 4]
Output: [1,5]    
Notice
There is at least one subarray that it's sum equals to zero.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(n)

Answer

class Solution {
public:
    vector<int> subarraySum(vector<int> &nums) {
        vector<int> prefix;
        int sum = 0;
        prefix.push_back(sum);
        for (auto i : nums) {
            sum += i;
            prefix.push_back(sum);
        }

        unordered_map<int, int> hash;
        for (int i = 0; i < prefix.size(); i++) {
            if (hash.find(prefix[i]) != hash.end()) 
                return {hash[prefix[i]], i - 1};
            hash[prefix[i]] = i;
        }
    }
};

tags: other

​