Q560-和为K的子数组-中等-动态规划

560. 和为K的子数组

类似题目：Q1546-和为目标值的最大数目不重叠非空子数组数目

Question

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

Example 1:

输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

Note:

数组的长度为 [1, 20,000]。

数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

Approach 1: 枚举

考虑以 i 结尾和为 k 的连续子数组个数，我们需要统计符合条件的下标 j 的个数，其中且这个子数组的和恰好为 k 。

我们可以枚举里所有的下标 j 来判断是否符合条件，可能有读者会认为假定我们确定了子数组的开头和结尾，还需要的时间复杂度遍历子数组来求和，那样复杂度就将达到从而无法通过所有测试用例。但是如果我们知道子数组的和，就能推出的和，因此这部分的遍历求和是不需要的，我们在枚举下标 j 的时候已经能求出的子数组之和。

class Solution:
    def subarraySum(self, nums, k):
        count=0
        for start in range(len(nums)):
            sum=0
            for end in range(start,-1,-1):
                sum+=nums[end]
                if sum == k:
                    count+=1
        return count


def main():
    nums = [-1,3,5,1,4,2,-9]
    target = 6
    solution=Solution().subarraySum(nums,target)
    print(solution)


if __name__ == "__main__":
    main()

复杂度分析

时间复杂度：，其中 n 为数组的长度。枚举子数组开头和结尾需要的时间，其中求和需要的时间复杂度，因此总时间复杂度为。
空间复杂度：。只需要常数空间存放若干变量。

Approach 2: 前缀和 + 哈希表优化

我们可以基于方法一利用数据结构进行进一步的优化，我们知道方法一的瓶颈在于对每个 i，我们需要枚举所有的 j 来判断是否符合条件，这一步是否可以优化呢？答案是可以的。

我们定义为里所有数的和，则可以由递推而来，即：

那么「这个子数组和为 k 」这个条件我们可以转化为所以我们考虑以 i 结尾的和为 k 的连续子数组个数时只要统计有多少个前缀和为的即可。我们建立哈希表，以和为键，出现次数为对应的值，记录出现的次数，从左往右边更新边计算答案，那么以 i 结尾的答案即可在时间内得到。最后的答案即为所有下标结尾的和为 k 的子数组个数之和。

需要注意的是，从左往右边更新边计算的时候已经保证了里记录的的下标范围是。同时，由于的计算只与前一项的答案有关，因此我们可以不用建立数组，直接用变量来记录的答案即可。

class Solution:
    def subarraySum1(self, nums, k):
        mp = {0: 1}
        count = 0
        pre = 0
        for x in nums:
            pre+=x
            if (pre - k) in mp:
                count += mp[pre - k]
            if pre in mp:
                mp[pre] += 1
            else:
                mp[pre] = 1
        return count


def main():
    nums = [-1,3,5,1,4,2,-9]
    target = 6
    solution=Solution().subarraySum1(nums,target)
    print(solution)


if __name__ == "__main__":
    main()

复杂度分析

时间复杂度：，其中 n 为数组的长度。我们遍历数组的时间复杂度为，中间利用哈希表查询删除的复杂度均为，因此总时间复杂度为。
空间复杂度：，其中 n 为数组的长度。哈希表在最坏情况下可能有 n 个不同的键值，因此需要的空间复杂度。