问题

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

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

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

示例 1 :

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

解法

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

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

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

也可以用官方库函数计算前缀和数组preSum=list(itertools.accumulate(nums,initial=0))等效于以下代码：

1
2
3
4
n=len(nums)
preSum=[0]*(n+1)   # 构造前缀和数组preSum
	for i in range(n):
		preSum[i+1]=nums[i]+preSum[i]