Subarray Sum

LintCode 138

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.

Notice

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

Example

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

Prefix sum 首题。这题用 prefix sum 和 hash map 解。

    def subarraySum(self, nums):
        prefix = 0
        hashmap = {0:0}
        for i in range(len(nums)):
            prefix += nums[i]
            if prefix in hashmap:
                return [hashmap[prefix], i]
            hashmap[prefix] = i + 1

        return [-1, -1]