LeetCode 974. 和可被 K 整除的子数组

2026-08-27 HGNULB 约 4 分钟

文章信息 9 个分类 3 个标签

分类

题目描述

✅ 974. 和可被 K 整除的子数组

题意分析

输入一个整数数组和正整数 k，要统计有多少个非空连续子数组，其元素和能被 k 整除。注意统计的是数量而不是长度，也不要求子数组互不重叠。

约束信号：数组长度可达数万，$O(n^2)$ 枚举所有子数组会超时，必须做到线性；元素可以是负数，这一点直接决定了实现细节。

负数带来的坑必须先说清楚：Java 和 Go 的 % 都是「截断取余」，符号跟随被除数，所以 -1 % 5 得到的是 -1 而不是数学意义上的 4。而本题的整个思路建立在「按余数分组」上，同一个数学余数必须映射到同一个桶里，因此每次取模后都要用 ((x % k) + k) % k 把结果修正到 [0, k - 1]。用数组计数时不修正会直接负下标越界，用哈希表计数时不会崩但会把 -1 和 4 当成两类，答案偏小。

边界包括：从下标 0 开始的子数组（没有「前一个前缀」可减）；整个数组和恰好被 k 整除；数组中出现 0；多个前缀落在同一余数上需要按组合数累计。

解法：前缀和余数计数

核心思路

设前缀和为 $P_i$，区间 [i + 1, j] 的和是 $P_j - P_i$。它能被 k 整除，当且仅当两个前缀和除以 k 的余数相同。因此无需枚举区间，只要从左到右统计每种余数出现过多少次。

当前前缀余数为 r 时，历史上每个余数同为 r 的前缀都能与它组成一个合法子数组，所以先执行 ans += count[r]，再执行 count[r]++。初始化 count[0] = 1 表示空前缀，可统一统计从下标 0 开始的区间。

Java 和 Go 对负数取余可能得到负值，必须用 ((x % k) + k) % k 把余数规范到 [0, k - 1]。

循环不变量：处理当前元素前，count[r] 记录所有历史前缀中规范余数为 r 的数量，ans 记录此前所有合法子数组；处理后，两者继续满足该定义。

解题步骤

创建长度为 k 的计数数组，令 count[0] = 1。

用 remainder 滚动维护前缀余数，不必保存完整前缀和数组。

读入 num 后，计算并规范化新余数。

把历史同余前缀数量 count[remainder] 加入答案。

再登记当前前缀：count[remainder]++。

对 nums = [4,5,0,-2,-3,1]、k = 5，规范余数依次为 4,4,4,2,4,0。每次加入该余数此前出现次数，贡献依次为 0,1,2,0,3,1，总数为 7。

代码实现

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)$，每个元素只处理一次。

空间复杂度：$O(k)$，计数数组为每种可能的余数保存一个计数。

关键点总结

核心等价关系：区间和被 k 整除，当且仅当区间两端的前缀和同余。

count[0] = 1 是空前缀，负责统计从下标 0 开始的合法区间。

必须先累计历史次数、再登记当前前缀，否则会把空子数组计入答案。

若某个余数最终出现 m 次，其贡献是 $m(m-1)/2$；在线累加历史次数正是逐项计算这个值。

易错点总结

不规范负余数会导致数组负下标，或把数学上同余的 -1 与 k - 1 分进不同桶。

用 abs 修正余数是错误的；例如模 5 时，-3 应归入 2，而不是 3。

忘记 count[0] = 1 会漏掉所有从下标 0 开始且和能整除 k 的子数组。

先增加计数再累加答案，会让当前前缀与自身配对，每个位置都多算一个空子数组。

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	前缀和差值配对计数
523. 连续的子数组和	中等	余数首次出现位置
1590. 使数组和能被 P 整除	中等	删最短子数组补齐余数
525. 连续数组	中等	0/1 映射后求等值前缀
930. 和相同的二元子数组	中等	计数与滑动窗口互换
1074. 元素和为目标值的子矩阵数量	困难	二维压缩成一维前缀和