Lintcode: 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.

Example

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

Note

There is at least one subarray that it's sum equals to zero.

Tags Expand 

Subarray Hash Table

Intuitive solution:

Try all possible subarrays with two loops.
Time: O(n2)
Space: O(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
        vector<int> result;
        int i, j;
        for(i = 0; i < nums.size(); i++){
            int sum = 0;
            for(j = i; j < nums.size(); j++){
                sum += nums[j];
                if(sum == 0) {
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }
            }
        }
        return result;
    }
};

Hashmap 
http://www.code123.cc/docs/leetcode-notes/integer_array/zero_sum_subarray.html#
If subarray sum equals 0, it means sum from 0 to i will have at lease two same sums.
So we can just use hashmap to record sums from 0 to i and check repeat.
if sum(0-i) = sum(0-j),  array[(i+1) - j] sums 0.  Here i >= 0.
This relationship exists when subarray starts from 1.
But if we set i >= -1, then sum(-1 to i) = sum(-1 to j), array[(i+1) to j] sums 0. Here i >= -1.
Then subarray starts from 0.

Note: With hashmap, we can check repetitive sum. If the subarray(sum is 0) starts from the beginning of the array, the sum before the beginning of the array is not in hashmap. We can set it 0.
Time: O(n)
Space: O(n)

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;
        unordered_map<int, int> hash;
        hash[0] = -1;
        int sum = 0;
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i];
            if(hash.find(sum) != hash.end()){
                result.push_back(hash[sum] + 1);
                result.push_back(i);
                return result;
            }
            hash[sum] = i;
        }
        return result;
    }
};

Sorting:
Record all the sums from 0 to i with a vector O(n) and then sort it. O(nlogn)
Then compare the sorted results and get subarray.O(n)
Time: O(nlogn)
space: O(n)