0560：和为 K 的子数组（★）

2016-07-13 约 289 字预计阅读 1 分钟次阅读

力扣第 560 题

题目

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

子数组是数组中元素的连续非空序列。

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

分析

#1

求任意子数组的和，容易想到前缀和。得到前缀和数组 pre 后，就是找 i < j 使得 pre[j]-pre[i]==k。

查找定值容易想到哈希表，遍历时边存边查即可。

1
2
3
4
5
6
7


def subarraySum(self, nums: List[int], k: int) -> int:
	pre = list(accumulate([0]+nums))
	res, ct = 0, Counter()
	for val in pre:
		res += ct[val-k]
		ct[val] += 1
	return res

116 ms

#2

也可以合并为一趟解决。

解答

1
2
3
4
5
6
7


def subarraySum(self, nums: List[int], k: int) -> int:
	res, pre, ct = 0, 0, Counter([0])
	for val in nums:
		pre += val
		res += ct[pre-k]
		ct[pre] += 1
	return res

116 ms

目录

0560：和为 K 的子数组（★）

题目

分析

#1

#2

解答