Subarray Sum

Question

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

Thoughts

一开始看到我以为用DP做，DP[i][j]表示 i 到 j 的sum, 这个解法需要O(n^2)

后来搜了一下发现了一个O(n)的解法，用hashmap存0-i的sum,如果某个sum之前出现过，就说明这之间有0 sum的subarray

Solution

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
        if not nums:
            return None
        length = len(nums)
        if length == 1:
            if nums[0] == 0:
                return [0, 0]
        dic = {}
        sumArr = [0 for i in range(length)]
        sumArr[0] = nums[0]
        dic[sumArr[0]] = 0
        for j in range(1, len(nums)):
            sumArr[j] = sumArr[j-1] + nums[j]
            if sumArr[j] in dic:
                i = dic[sumArr[j]]
                #from i + 1 to j is the 0 subarray 
                return [i + 1, j]
            if sumArr[j] == 0:
                #current subarray is the 0 subarray
                return [0, j]
            #put into dictionary
            dic[sumArr[j]] = j