def subarraySum(self, nums):
        """
        DP:
        DP + Hash
         reduce from O(n^2) to O(n)

        :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
        """
        n = len(nums)
        f = [0 for _ in xrange(n+1)]
        for i in xrange(1, n+1):
            f[i] = f[i-1]+nums[i-1]

        d = defaultdict(list)
        for i in xrange(1, n+1):
            d[f[i]].append(i)

        for k, v in d.items():
            if k == 0:
                return [0, v[0]-1]
            if len(v) > 1:
                return [v[0], v[1]-1]

        return [-1, -1]
dataset/ETHPy150Open algorhythms/LintCode/Subarray Sum.py/Solution.subarraySum/original