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

Solution

题目理解：Subarray 一定是连续的，一个范围的，找到头尾索引。

使用Hash表解题，如果一段区间的和为零，那么Hash表，值i 经过零区间，一定会有重复的Key。

(1)I can only figure out a way is O(n2) method,

(2) it's very import do a new sum array , the duplicates of that array would be the index range

(3) I used two for loop which is wrong , we can do it within 1 for loop and also the return, we can use hashtable do the same thing.

class Solution:
    """
    @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
    """
    def subarraySum(self, nums):
        # write your code here
        d = {0:-1}
        n = len(nums)

        sum = 0

        for i in range(n):
            sum += nums[i]
            if sum in d:
                return [d[sum] + 1, i]
            d[sum] = i
        return [-1, -1]