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.

分析：

第二遍刚做的时候，带着subarray的想法，上来先写了个O(n^2)的方法2，结果空间复杂度超了，没过去大数据的case。

方法1的时间复杂度是O(n)，空间复杂度也是，这个方法很不错，他的思路是记录每一步的subarray sum，一旦两次subarray sum相等，则说明中间这段subarray的sum是0。

这个方法需要注意第一个元素为0的情况，要么刚开始就hash[0] = -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.size() == 0) {
            return vector<int>();
        }
        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() ) {
                vector<int> res(2, 0);
                res[0] = Hash[sum] + 1;
                res[1] = i;
                return res;
            }
            Hash[sum] = i;
        }
        return vector<int>();
    }
};

解法2：

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
        int n = nums.size();
        if (n == 0) {
            return vector<int>();
        }
        vector<vector<int> > sum(n, vector<int>(n, INT_MIN) );
        for (int i = 0; i < n; i++) {
            sum[i][i] = nums[i];
            if (nums[i] == 0) {
                return vector<int>(2, i);
            }
        }
        vector<int> res(2, -1);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                sum[i][j] = sum[i][j - 1] + nums[j];
                if (sum[i][j] == 0) {
                    res[0] = i;
                    res[1] = j;
                    break;
                }
            }
        }
        return res;
    }
};