【LintCode 简单】138. 子数组之和

ゞ浴缸里的玫瑰 2022-06-01 00:10 195阅读 0赞

1.问题描述：

给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置。

2.样例：

给出 `[-3, 1, 2, -3, 4]`，返回`[0, 2]` 或者 `[1, 3]`.

3.代码：

方法一：

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
            length=len(nums)
            j = 0
            if length==1 and nums[0]==0:
                location = [0,0]
                return location
            else:
                while j < length-1:
    	            sum = 0
    	            for i in range(j,length):
    		            sum = sum + nums[i]
    		            if sum == 0:
    			            location = [j, i]
    			            return location
    	            j=j+1

方法二：

用字典存储中间结果。key为从第一个元素到当前元素的和，value为下标。当某个key值第二次出现时，则它们中间的子数组和一定为0。

方法二的时间复杂度比方法一更加优化。

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
            res = []
            if nums is None or len(nums) <= 0:
                return res
            d = {0: -1}
            sum = 0
            for i in range(len(nums)):
                sum += nums[i]
                if sum in d:
                    res.append(i)
                    res.append(d[sum] + 1)
                    return res
                d[sum] = i
            return res