LeetCode 974. 和可被 K 整除的子数组
题目描述
题意分析
统计元素和能被
k整除的非空连续子数组数量，和为零也符合要求。数组含有负数，区间扩大时和不一定增加，不能依靠和的大小来移动窗口。可以把区间和写成两个前缀和之差，再按除以
k的余数统计前缀，避免枚举每个区间。
解法：前缀和余数计数
核心思路
[!blue]
设 $P[i]$ 是前 $i$ 个元素之和，且 $P[0]=0$。区间
[l, r)的和为 $P[r]-P[l]$，它能被k整除，当且仅当这两个前缀和对k同余。遍历到当前前缀时，
count[t]记录此前余数为t的前缀数量。若当前余数为remainder，每个历史同余前缀都对应一个不同的左端点，因此恰好新增count[remainder]个合法子数组。按右端点依次统计，每个区间只会被计入一次。必须先累计答案，再登记当前前缀，这样配对的前缀才严格位于当前前缀之前，不会算入长度为零的区间。初始化
count[0] = 1表示空前缀，让从数组开头开始的合法区间也能通过同一规则计入。只保存前缀余数即可：加上新元素再取模，与先求完整前缀和再取模等价。Java 和 Go 的负数取余可能得到负值，因此用
((remainder + num) % k + k) % k统一到[0, k - 1]，使数学上同余的前缀落在同一位置。
解题步骤
- 创建长度为
k的计数数组，令count[0] = 1。- 用
remainder滚动维护前缀余数，不必保存完整前缀和数组。- 读入
num后，计算并规范化新余数。- 把历史同余前缀数量
count[remainder]加入答案。- 再登记当前前缀：
count[remainder]++。
代码实现
class Solution {
public int subarraysDivByK(int[] nums, int k) {
int[] count = new int[k];
count[0] = 1;
int remainder = 0;
int ans = 0;
for (int num : nums) {
remainder = ((remainder + num) % k + k) % k;
// 相同余数的两个前缀和相减，子数组和一定能被 k 整除。
ans += count[remainder];
// 先累计历史同余前缀，最后登记当前值，避免算入空区间。
count[remainder]++;
}
return ans;
}
}
func subarraysDivByK(nums []int, k int) int {
count := make([]int, k)
count[0] = 1
remainder := 0
ans := 0
for _, num := range nums {
remainder = ((remainder+num)%k + k) % k
// 相同余数的两个前缀和相减，子数组和一定能被 k 整除。
ans += count[remainder]
// 先累计历史同余前缀，最后登记当前值，避免算入空区间。
count[remainder]++
}
return ans
}
复杂度分析
- 时间复杂度：$O(n+k)$，初始化
k项计数数组，再逐个处理n个元素。- 空间复杂度：$O(k)$，计数数组为每种可能的余数保存一个计数。
关键点总结
[!green]
- 核心等价关系：区间和被
k整除，当且仅当区间两端的前缀和同余。count[0] = 1是空前缀，负责统计从下标 0 开始的合法区间。- 必须先累计历史次数、再登记当前前缀，否则会把空子数组计入答案。
- 若某个余数最终出现
m次，其贡献是 $m(m-1)/2$；在线累加历史次数正是逐项计算这个值。
易错点总结
[!yellow]
- 不规范负余数会导致数组负下标，或把数学上同余的
-1与k - 1分进不同桶。- 用
abs修正余数会改变它所属的同余类；应加k后再取模。- 忘记
count[0] = 1会漏掉所有从下标 0 开始且和能整除k的子数组。- 先增加计数再累加答案，会让当前前缀与自身配对，每个位置都多算一个空子数组。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 523. 连续的子数组和 | 中等 | 同样比较前缀余数，原题只判是否存在且长度至少2，本题累计所有非空子数组。 |
| 560. 和为 K 的子数组 | 中等 | 本题把精确前缀差相等改为模k同余，仍通过前缀频次统计区间。 |
| 1590. 使数组和能被 P 整除 | 中等 | 按前缀和余数分类；本题统计同余前缀对数，该题查找应删区间的余数差并最小化长度。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！