0974. Subarray Sums Divisible by K¶
题目信息¶
- 题号:
0974
- 难度:
Medium
- 主题:
数组、连续子数组、整除计数
- 原题:
- 重点:
统计所有非空连续子数组实例,其元素和必须能被正整数
k整除;数组允许包含负数和零
题目重述¶
给定整数数组 nums 和正整数 k。请统计有多少个非空连续子数组的元素总和能够被 k 整除,即总和除以 k 的余数为 0。
子数组由起止下标确定,不同下标范围分别计数。元素可以为负数,和为 0 的子数组也满足整除条件。
1 <= nums.length <= 3 * 10^4,-10^4 <= nums[i] <= 10^4,2 <= k <= 10^4。
自建示例¶
负数使多个区间的和成为三的倍数:
输入:nums = [2,-2,3,1], k = 3
输出:3
解释:合法子数组为 nums[0..1],和为 0;nums[0..2],和为 3;以及 nums[2..2],和为 3。
全部元素都是零:
输入:nums = [0,0,0], k = 2
输出:6
解释:三个单元素、两个长度为 2 的区间和整个数组的和都为 0,因此六个非空子数组全部满足整除条件。