目录

0974:和可被 K 整除的子数组(1675 分)

力扣第 119 场周赛第 3 题

题目

给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的非空 子数组 的数目。

子数组 是数组中 连续 的部分。

示例 1:

输入:nums = [4,5,0,-2,-3,1], k = 5
输出:7
解释:
有 7 个子数组满足其元素之和可被 k = 5 整除:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2:

输入: nums = [5], k = 9
输出: 0

提示:

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • 2 <= k <= 104

相似问题:

分析

类似 0523 和 0560 ,用哈希表保存前缀和的个数即可。

解答

1
2
3
4
5
6
7
def subarraysDivByK(self, A: List[int], K: int) -> int:
	res, s, d = 0, 0, defaultdict(int)
	for num in A:
		d[s] += 1
		s = (s+num) % K if K else s+num
		res += d[s]
	return res

324 ms