题目
给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1:
输入:nums = [1,1,1], k = 2
输出:2
示例 2:
输入:nums = [1,2,3], k = 3
输出:2
提示:
1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7
思路
一:暴力解法:双层循环,超时
二:前缀和:超时
三:前缀和化+字典
前缀和可知,pre[i]=pre[i-1]+nums[i]
由j与i之间的子数组和为k 这个条件可以转化为 pre[i]-pre[j-1]=k简单移项可得符合条件的下标j需要满足pre[j-1] = pre[i]-k。所以我们考虑以i结尾的和为k的连续子数组的个数时只要统计有多少个前缀和为pre[i]-k的pre[j]即可。因此我们在计算时便可以用一个字典来实现pre[j]的值以及其个数,当我们遍历到nums[i]时可以以O(1)的时间找到在此之前pre[i]-k的个数,即求得以nums[i]为子数组右边界且满足和为k的子数组个数
代码
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
res = 0
import collections
n = len(nums)
presum = 0
preSum = collections.defaultdict(int)
preSum[0] = 1
for i in range(n):
presum+=nums[i]
if(presum-k in preSum ):
res+=preSum[presum-k]
preSum[presum]+=1
return res
标签:pre,md,nums,560,int,数组,presum,热题,preSum
From: https://www.cnblogs.com/anamzingclown/p/17578457.html