Zero Sum Subarray

Question

• lintcode: (138) Subarray Sum
• GeeksforGeeks: Find if there is a subarray with 0 sum - GeeksforGeeks

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.

题解1 - 两重 for 循环

题目中仅要求返回一个子串(连续)中和为0的索引，而不必返回所有可能满足题意的解。最简单的想法是遍历所有子串，判断其和是否为0，使用两重循环即可搞定，最坏情况下时间复杂度为 $$O(n^2)$$, 这种方法显然是极其低效的，极有可能会出现 TLE. 下面就不浪费篇幅贴代码了。

题解2 - 比较子串和(TLE)

两重 for 循环显然是我们不希望看到的解法，那么我们再来分析下题意，题目中的对象是分析子串和，那么我们先从常见的对数组求和出发，$$f(i) = \sum _{0} ^{i} nums[i]$$ 表示从数组下标 0 开始至下标 i 的和。子串和为0，也就意味着存在不同的 $$i_1$$ 和 $$i_2$$ 使得 $$f(i_1) - f(i_2) = 0$$, 等价于 $$f(i_1) = f(i_2)$$. 思路很快就明晰了，使用一 vector 保存数组中从 0 开始到索引i的和，在将值 push 进 vector 之前先检查 vector 中是否已经存在，若存在则将相应索引加入最终结果并返回。

题解3 - 哈希表

终于到了祭出万能方法时候了，题解2可以认为是哈希表的雏形，而哈希表利用空间换时间的思路争取到了宝贵的时间资源 :)

• reference
• visualization

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, A):
        hs = {0:-1}
        sum = 0
        for i in range(len(A)):
            # if A[i] == 0:
            #     return [i, i]
            sum += A[i]
            if sum in hs:
                return [hs[sum] + 1, i]
            hs[sum] = i
        return

sol=Solution()
A=[-3, 1, 2, -3, 4]
sol.subarraySum(A)