LeetCode 560. 和为 K 的子数组

题目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

例：
输入：nums = [1,1,1], k = 2
输出：2

方法一：暴力解法

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

※ 超出时间限制

方法二：前缀和

• count 记录符合题目的连续子数组的数量
• preSums 字典，记录每个前缀和出现的次数
• presum 记录从数组 nums 的第一个数开始到下标 i 对应的数的和，即前缀和。初始值为 0
• 循环遍历数组
  • 计算前缀和
  • 计算符合题目的连续子数组的数量 count。根据前缀和的定义，若我们想要得到和为 k 的连续子数组，假设 [i, j] 连续子数组的和为 k，那么 presumj - presum(i-1) = k，所以我们只需要判断 presumj - k = presum(i-1) 的这个 presum(i-1) 是否存在即可，即通过 preSums 查看次数。该次数就是本次符合题目的连续子数组的数量
  • 将此时的前缀和加入字典 preSums

class Solution(object):
    def subarraySum(self, nums, k):
        count = 0
        preSums = collections.defaultdict(int)
        preSums[0] = 1
        presum = 0
        for i in range(len(nums)):
            presum += nums[i]
            count += preSums[presum-k]
            preSums[presum] += 1      
        return count

相关知识

• 前缀和：
  一个数组的某下标之前的所有数组元素的和（包含其自身）。通常，会在前缀和首位放一个0

• defaultdict(factory_function)： collections.defaultdict()
  功能与dict相同，但会为一个不存在的键提供默认值，从而避免KeyError异常
  factory_function： 提供初始值，默认为 None。可以为 int、str、list 等，若为 int，当键不存在时，其值为 0；同理，若为 list，当键不存在时，其值为 []

参考

代码相关：https://leetcode.cn/problems/subarray-sum-equals-k/solution/python3-by-wu-qiong-sheng-gao-de-qia-non-w6jw/
defaultdict：https://blog.csdn.net/u014248127/article/details/79338543 https://blog.csdn.net/jiaxinhong/article/details/108398099