问题

给定一个数组,求和等于目标值连续子数组的个数。

力扣中等题:560. 和为K的子数组

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

示例 1 :

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

解法

比较容易想到的是暴力解法,循环遍历得到所有的子数组的和,如果正好等于目标值则让计数加一,最后返回计数值。一般是用2个指针ij分别指向指向子数组的开头和结尾,内外两层循环,时间复杂度为

1
2
3
4
5
6
7
8
9
10
def subarraySum(self, nums: List[int], target: int) -> int:
n=len(nums)
res=0
for i in range(n):
s=0
for j in range(i,n):
s+=nums[j]
if s==target:
res+=1
return res

暴力法的时间复杂度过高,实际上我们可以预先处理数组,得到一个前缀和数组,在这个数组的基础上去计算,将时间复杂度降到

前缀和数组每一项对应的是数组从第0项累加到第i项的和,preSum[i]=sum(nums[0]+nums[1]+...+nums[i]),比如[1,2,3,4,5]的前缀和数组是[1,3,6,10,15]。得到了这个数组,我们就可以以的时间复杂度求任意子数组的和,比如sum(nums[2],nums[3],nums[4])=preSum[4]-preSum[1],也就是说,对于任意的连续子数组nums[i,j],它的和等于preSum[j]-preSum[i-1]

我们可以为preSum开头补充一项0,这样preSum[i]表示的意义为数组前i个数字的和,连续子数组nums[i,j]的和就可以表示为preSum[j+1]-preSum[i],省去了边界检查。

sum(nums[2,4])=preSum[4+1]-preSum[2]

对于任意一个子数组的和为S[i,j]等于目标值target,有S[i,j]=preSum[j+1]-preSum[i]=target,则preSum[i]=preSum[j+1]-target。我们可以遍历preSum数组,对于任意一个j,记录对应有多少个preSum[i]值可以满足条件preSum[i]=preSum[j+1]-target,i<=j(i可以等于j,只有一项的数组我们也认为满足条件),总和即为结果。我们可以用一个哈希表来记录所有不同的preSum[i],同时存储个数,这样就省去了内循环的i值遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
def subarraySum(self, nums: List[int], target: int) -> int:
n=len(nums)
preSum=[0]*(n+1) # 构造前缀和数组preSum
for i in range(n):
preSum[i+1]=nums[i]+preSum[i]
counter=Counter() # 构造哈希表
counter[0]=1 # 初始化preSum[0]的个数为1
res=0
for j in range(n):
if (k:=preSum[j+1]-target) in counter: # k相当于preSum[i]
res+=counter[k] # 累加结果
counter[preSum[j+1]]+=1 # 当前的preSum值纳入统计
return res

可以看到,两个循环我们始终从preSum索引1开始遍历,索引0并没有用到,而且在第二个循环中,可以同步的去求preSum的值,所以可以将两个循环省略为一个。

1
2
3
4
5
6
7
8
9
10
11
12
def subarraySum(self, nums: List[int], target: int) -> int:
n=len(nums)
preSum=[0]*(n+1) # 构造前缀和数组preSum
counter=Counter() # 构造哈希表
counter[0]=1 # 初始化preSum[0]的个数为1
res=0
for j in range(n):
preSum[j+1]=nums[j]+preSum[j]
if (k:=preSum[j+1]-target) in counter: # k相当于preSum[i]
res+=counter[k] # 累加结果
counter[preSum[j+1]]+=1 # 当前的preSum值纳入统计
return res

在每次循环中,preSum的当前值preSum[j+1]是通过前一个值preSum[j]计算出来的,也就是说每次循环中,我们只需要用到preSum中的一个值即可,那就没必要存储整个preSum数组,这也是常见的采用滚动数组压缩空间的方式。

1
2
3
4
5
6
7
8
9
10
11
12
def subarraySum(self, nums: List[int], target: int) -> int:
n=len(nums)
preSum=0 # 压缩前缀和数组
counter=Counter() # 构造哈希表
counter[0]=1 # 初始化preSum[0]的个数为1
res=0
for j in range(n):
preSum+=nums[j]
if (k:=preSum-target) in counter: # k相当于preSum[i]
res+=counter[k] # 累加结果
counter[preSum]+=1 # 当前的preSum值纳入统计
return res

最终,利用前缀和的思想和哈希表的数据结构,该题的时间复杂度为,空间复杂度为哈希表的