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

相似问题：

• 0560：和为 K 的子数组
• 1590：使数组和能被 P 整除（2038 分）
• 2364：统计坏数对的数目（1622 分）
• 2575：找出字符串的可整除数组（1541 分）
• 2845：统计趣味子数组的数目（2073 分）

分析

类似 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