LeetCode 974中等前缀和/哈希
和可被 K 整除的子数组 图解题解
这道题到底在问什么
给定整数数组 nums 与正整数 k，统计「连续子数组的和能被 k 整除」的子数组个数。
- 输入
- nums=[4,5,0,-2,-3,1], k=5
- 输出
- 7
先想最直接的笨办法
全程扫完，累计答案 = 12。每一步都把「当前余数的历史出现次数」加进答案——同余配对，一遍 O(n) 就数清了，无需枚举所有子数组。（动画第 25 步）
最优解：一步一步想明白
- 3记住「同余即可整除:答案 += 该余数已出现次数,再让它 +1」,下面每帧都在套它。
- 4开局把「余数 0 出现 1 次」放进表里——这代表「空前缀」，它让那些「从数组开头起就能被 k 整除」的子数组也能被正确数到。
- 5读第 0 个 4，更新前缀和、对 5 取余得余数 4（表中高亮那行）。表里余数 4 已出现 0 次——意味着前面有 0 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。
- 6结算：余数 4 之前没出现过（加 0，答案仍 0）；把它记进表（现 1 次），等后面有相同余数再来配。
- 7读第 1 个 5，更新前缀和、对 5 取余得余数 4（表中高亮那行）。表里余数 4 已出现 1 次——意味着前面有 1 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。
- 8结算：答案加上 1，变成 1；再把当前这个余数 4 记进表（现 2 次），供后面的元素配对。
- 9读第 2 个 0，更新前缀和、对 5 取余得余数 4（表中高亮那行）。表里余数 4 已出现 2 次——意味着前面有 2 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。
- 10结算：答案加上 2，变成 3；再把当前这个余数 4 记进表（现 3 次），供后面的元素配对。
- 11读第 3 个 -2，更新前缀和、对 5 取余得余数 2（表中高亮那行）。表里余数 2 已出现 0 次——意味着前面有 0 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。
- 12结算：余数 2 之前没出现过（加 0，答案仍 3）；把它记进表（现 1 次），等后面有相同余数再来配。
- 13读第 4 个 -3，更新前缀和、对 5 取余得余数 4（表中高亮那行）。表里余数 4 已出现 3 次——意味着前面有 3 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。
- 14结算：答案加上 3，变成 6；再把当前这个余数 4 记进表（现 4 次），供后面的元素配对。
- 15读第 5 个 1，更新前缀和、对 5 取余得余数 0（表中高亮那行）。表里余数 0 已出现 1 次——意味着前面有 1 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。
- 16结算：答案加上 1，变成 7；再把当前这个余数 0 记进表（现 2 次），供后面的元素配对。
- 17读第 6 个 2，更新前缀和、对 5 取余得余数 2（表中高亮那行）。表里余数 2 已出现 1 次——意味着前面有 1 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。
- 18结算：答案加上 1，变成 8；再把当前这个余数 2 记进表（现 2 次），供后面的元素配对。
- 19读第 7 个 6，更新前缀和、对 5 取余得余数 3（表中高亮那行）。表里余数 3 已出现 0 次——意味着前面有 0 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。
- 20结算：余数 3 之前没出现过（加 0，答案仍 8）；把它记进表（现 1 次），等后面有相同余数再来配。
- 21读第 8 个 4，更新前缀和、对 5 取余得余数 2（表中高亮那行）。表里余数 2 已出现 2 次——意味着前面有 2 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。
- 22结算：答案加上 2，变成 10；再把当前这个余数 2 记进表（现 3 次），供后面的元素配对。
- 23读第 9 个 3，更新前缀和、对 5 取余得余数 0（表中高亮那行）。表里余数 0 已出现 2 次——意味着前面有 2 个前缀和它同余，各能和现在配成一个能被 5 整除的子数组。
- 24结算：答案加上 2，变成 12；再把当前这个余数 0 记进表（现 3 次），供后面的元素配对。
- 25全程扫完，累计答案 = 12。每一步都把「当前余数的历史出现次数」加进答案——同余配对，一遍 O(n) 就数清了，无需枚举所有子数组。
⚠️ 容易写错的地方
✗ 错：忘了 count[0] 初始化为 1
✓ 对：count[0]=1 代表空前缀
否则「从开头起就整除」的子数组会漏数
✗ 错：负数取模直接用 %
✓ 对：用 ((x%k)+k)%k 归一到非负
很多语言里负数 % 结果为负，会落到错误的余数桶
✗ 错：先 count[rem]++ 再 ans += count[rem]
✓ 对：必须先加答案再自增
否则把当前前缀自己也算进配对，多计一次
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def subarraysDivByK(self, nums: List[int], k: int) -> int:
count = [0] * k
count[0] = 1
prefix = ans = 0
for x in nums:
prefix = (prefix + x) % k
ans += count[prefix]
count[prefix] += 1
return ansC++
#include <vector>
using namespace std;
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
vector<int> count(k);
count[0] = 1;
int prefix = 0, ans = 0;
for (int x : nums) {
prefix = ((prefix + x) % k + k) % k;
ans += count[prefix];
count[prefix]++;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int subarraysDivByK(int[] nums, int k) {
int[] count = new int[k];
count[0] = 1;
int prefix = 0, ans = 0;
for (int x : nums) {
prefix = ((prefix + x) % k + k) % k;
ans += count[prefix];
count[prefix]++;
}
return ans;
}
}复杂度
时间
O(n)
扫一遍数组
空间
O(k)
余数计数表大小为 k
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 和可被 K 整除的子数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
和「和为 K 的子数组(LC560)」有什么异同？+
同样是前缀和 + 哈希一遍扫。LC560 哈希存「前缀和的值」、找差等于 K；本题存「前缀和模 k 的余数」、找同余。一个看差值、一个看同余，模板一致只是键不同。
为什么用长度为 k 的数组而不是哈希表？+
余数只有 0..k−1 共 k 种，用数组当桶即可 O(1) 读写、且省哈希开销；当 k 很大或键稀疏时也可换成哈希表，思路不变。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 和可被 K 整除的子数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。