👋 欢迎阅读
🎯 欢迎来到「和可被 K 整除的子数组」题解之旅！本文将带你从"数一数有多少段连续数字的和能被 K 整除"这一直观场景出发，深入理解前缀和 + 同余计数的巧妙运用，并掌握如何用修正后的余数做哈希计数来在 O(n) 内统计全部子数组。
在开始之前，建议你先：
了解题目背景：这是 LeetCode 974 题，给定整数数组
nums和整数k，统计并返回和能被k整除的连续子数组的个数。本质上，(前缀和(i) - 前缀和(j-1)) % k == 0等价于两个前缀和对 k 同余，问题转化为统计余数相同的配对数量。明确学习目标：掌握前缀和余数计数技术，理解
(sum % k + k) % k修正负余数的原因与hash[0] = 1 的初始化，并熟练处理负数元素与k 为负等边界情况。准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如
nums = [4,5,0,-2,-3,1]，k = 5输出7）。
本文将从问题转化、同余计数、余数修正、边界防护到代码实现，层层递进。即使你对同余原理还不熟悉，我们也会从"两个账本余数相同，中间那段就整除了"这一直觉出发，让你轻松抓住核心思想——余数相同即整除，计数配对得答案。现在，让我们一起统计余数，数出所有能被 K 整除的子数组吧！ 🔢🎯
🏠个人主页：愿旖旎
📘专栏传送门：算法专栏
💻当前学习内容：前缀和
一.题目
974. 和可被 K 整除的子数组 - 力扣（LeetCode）
二、算法分析
一、问题分析（前置分析）
- 题目要求：统计
nums中和能被 k 整除的连续子数组个数。 - 关键约束：元素可能为负数（前缀和余数可能为负）；
k可能很大；计数可能很大。 - 核心思路：暴力做法枚举所有子数组求和判断整除，总代价 O(n²)；利用同余性质，
(sum[i] - sum[j-1]) % k == 0等价于sum[i] % k == sum[j-1] % k，用哈希表统计每个余数的出现次数，配对即得答案，总复杂度O(n)。
📌 例子：为什么"差为 k"变成"同余"
nums = [4, 5, 0, -2, -3, 1]，k = 5，前缀和为4、9、9、7、4、5。子数组[2..4]的和 =0 + (-2) + (-3) = -5能被 5 整除；看前缀和：sum[4] = 4与sum[1] = 4对 5 同余（都是 4），差4 - 4 = 0整除 5——两个前缀和同余 ⇔ 中间子数组和能被 k 整除，这就是本解法不枚举子数组的数学依据。
二、算法策略（前缀和余数 + 哈希计数）
核心步骤：
- 初始化：
hash[0] = 1（空前缀余数为 0）、sum = 0、ret = 0。 - 遍历累加：
sum += nums[i]得到当前前缀和。 - 修正余数：
r = (sum % k + k) % k（把负余数修正到 [0, k)，保证哈希键统一）。 - 查询配对：若哈希表存在余数
r，ret += hash[r]（与之前同余的前缀和每个都配对成一个子数组）。 - 记录当前：
hash[r]++（先查后插，保证子数组非空）。 - 返回：遍历结束返回
ret。
📊 示例（nums = [4, 5, 0, -2, -3, 1]，k = 5）：
| 步骤 | sum | r = (sum%5+5)%5 | 查询 hash[r] | hash 变化 | ret |
|---|---|---|---|---|---|
| 初始化 | 0 | — | — | {0:1} | 0 |
| i=0, x=4 | 4 | 4 | 查 4，无 | {0:1, 4:1} | 0 |
| i=1, x=5 | 9 | 4 | 查 4 →+1 | {0:1, 4:2} | 1 |
| i=2, x=0 | 9 | 4 | 查 4 →+2 | {0:1, 4:3} | 3 |
| i=3, x=-2 | 7 | 2 | 查 2，无 | {0:1, 4:3, 2:1} | 3 |
| i=4, x=-3 | 4 | 4 | 查 4 →+3 | {0:1, 4:4, 2:1} | 6 |
| i=5, x=1 | 5 | 0 | 查 0 →+1 | {0:2, 4:4, 2:1} | 7 |
最终ret = 7，与题目示例一致（每个配对对应一个可整除子数组）。
三、正确性说明（简单版本）
- 同余定理保证等价：
(sum[i] - sum[j-1]) % k == 0当且仅当sum[i] % k == sum[j-1] % k——差整除 ⇔ 余数相等，数学上严格成立，不会漏计也不会错计。 - 余数修正保持等价：
(sum % k + k) % k把 C++ 的负余数（如-1 % 5 = -1）修正为数学余数（4），同一前缀和的数学余数唯一，不同前缀和余数不同的关系不受影响，哈希键统一。 - 计数语义正确：
hash[r]表示"余数为 r 的历史前缀和个数"，ret += hash[r]精确统计所有与当前同余的历史前缀和——每个都对应一个和能被 k 整除的子数组，不重不漏。 - 先查后插 + hash[0]=1：保证子数组长度 ≥ 1且从起点开始的子数组（对应空前缀余数 0）也能被统计，覆盖全部情形。
📌 例子：为什么余数相同就一定是整除数
nums = [4, 5, 0, -2, -3, 1]，k = 5：sum[4] = 4、sum[1] = 4余数都是 4，配对 → 子数组[2..4]和= 0-2-3 = -5，-5 % 5 == 0✅。反之若余数不同（如 4 和 2），差% 5必不为 0，不可能构成整除数——同余是整除的充要条件。
四、实现细节（边界防护）
- 初始化：
hash[0] = 1（空前缀余数 0，处理从起点开始的子数组）、sum = 0、ret = 0。 - 边界防护：负余数修正
(sum % k + k) % k保证键落在[0, k)（C++ 中-3 % 5 = -3，不修正会键混乱）；先查后插保证子数组非空；k为负时sum % k符号仍随被除数，修正公式同样适用；哈希表键值可能很大（余数范围 [0, k)），用 int 足够。 - 复杂度：时间 O(n)（单次遍历，哈希操作均摊 O(1)），空间 O(n)（哈希表最多存 k 种余数）。
- 关键操作：
int r = (sum % k + k) % k;（余数修正）、if (hash.count(r)) ret += hash[r];（同余配对）、hash[0] = 1;（空前缀初始化）。
📌 例子：负数取模修正的必要性
sum = -3，k = 5：C++ 中-3 % 5 = -3（负余数），若直接用作哈希键，-3与数学余数2（-3 = -1×5 + 2）不是同一个键，同余配对会错乱；修正(-3 % 5 + 5) % 5 = (-3 + 5) % 5 = 2后，-3正确映射到余数2，与任何前缀和余数 2 的前缀正常配对——一行修正解决所有负数问题。
五、返回值（目标映射）
- 返回
ret：和能被 k 整除的子数组个数，对应题目"返回满足题意的子数组个数"。
三.代码
class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { unordered_map<int, int> hash; // 哈希表：记录每个前缀和余数出现的次数 int sum = 0; // 当前前缀和 int ret = 0; // 答案：和能被 k 整除的子数组个数 hash[0] = 1; // 空前缀余数为 0（处理从起点开始的子数组） // 1. 单次遍历：边累加前缀和，边统计同余配对 for (const auto& x : nums) { sum += x; // 当前位置的前缀和 // 2. 修正余数：C++ 取模可能为负，统一修正到 [0, k) int r = (sum % k + k) % k; // 3. 查询：之前是否存在同余的历史前缀和（差能被 k 整除） if (hash.count(r)) { ret += hash[r]; // 每个同余历史前缀和配对成一个子数组 } // 4. 记录当前余数（先查后插，保证子数组非空） hash[r]++; } return ret; // 5. 返回总子数组个数 } };四、易错点分析
难点1：为什么整除问题要转化为"同余"
if (hash.count(r)) // r = 当前前缀和余数 ret += hash[r];子数组
[j..i]的和能被 k 整除 ⇔(sum[i] - sum[j-1]) % k == 0⇔sum[i] % k == sum[j-1] % k（同余定理）。直接统计"差 = 0 的配对"需要两两比较 O(n²)，而统计"余数相等的配对"只需哈希表按余数分组，O(1) 查询——同余把"整除判断"变成"找相同余数"，这是复杂度骤降的关键。
难点2：(sum % k + k) % k为什么要修正两遍
int r = (sum % k + k) % k;C++ 的
%对负数结果是负余数（如-3 % 5 = -3），而数学余数应为非负（-3 = -1×5 + 2）。第一遍sum % k得带符号余数，+ k把负数拉回正区间，第二遍% k处理"加上 k 后恰好等于 k"的边界（如-1 % 5 + 5 = 4无需再模，但sum % k == 0时0 + k = k，需再模回 0）。只写sum % k或漏掉第二遍都会让键不一致，同余配对错乱。
难点3：hash[0] = 1的必要性（与 560 题同源）
hash[0] = 1; // 空前缀余数 0从起点开始的子数组（如
[0..i]的和能被 k 整除）对应"历史前缀和 = 0"，即空前缀。漏掉这行，sum % k == 0时查hash[0]永远为空，所有从起点开始的整除数子数组全部漏计——这是前缀和计数类题目的统一陷阱。
难点4：先查后插的顺序（与 560 题相同）
if (hash.count(r)) ret += hash[r]; hash[r]++; // 必须在查询之后若先
hash[r]++再查询，当前前缀和余数立即入表，与自身"配对"出空子数组（长度 0），多计 n 个非法答案。先查后插保证配对对象是严格更早的前缀和，子数组长度 ≥ 1，语义正确。
难点5：为什么存"次数"而非"布尔值"
ret += hash[r]; // 累加次数同一余数可能被多个历史前缀和拥有（如示例中余数 4 出现 4 次）。每个历史前缀和都对应一个不同的子数组起点，必须用次数累加；若只存"是否出现过"，重复余数对应的多个子数组全部漏计——这与 560 题的负数重复前缀和是同一类问题，都是"一数对多"的计数需求。
五、流程图
🎯 闭幕
🎉 恭喜你完成了「和可被 K 整除的子数组」问题的学习！
为了巩固知识并进一步拓展，建议你：
🚀动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。
💡深入思考
本题统计和能被 K 整除的子数组个数，利用前缀和余数的同余关系。请问
hash[0] = 1的含义是什么？为什么空前缀余数为 0 需要提前记录？如果不记录，会漏掉哪些子数组？代码中余数修正为
r = (sum % k + k) % k。为什么不能直接使用sum % k？在 C++ 中负数的取模结果是什么？请举例说明不修正会出现什么错误。遍历过程中，先查询
r再插入当前r，这个顺序为什么重要？如果先插入再查询，会有什么后果（特别当k为 1 或余数为 0 时）？哈希表记录的是余数的出现次数，而不是前缀和本身。为什么用余数次数就可以配对？两个前缀和余数相同意味着什么？
如果数组中包含0，当前算法是否仍然正确？请结合
nums=[0,0],k=1验证。
如果你觉得本文对你有所帮助，欢迎：
👍点赞 / 收藏
👤关注作者，获取更多题解
💬留言交流你的疑问或优化思路
📌深入思考答案
hash[0]=1表示空前缀余数为 0 出现过一次，用于处理从数组开头（下标 0）开始的子数组。例如nums=[4,5],k=3，前缀和依次为 4,9，余数分别为 1,0；当遍历到第二个元素时，r=0，查询hash[0]命中（来自空前缀），计数 +1，对应子数组[4,5]和为 9 可被 3 整除，若不存 0 则漏计。必须修正负数取模，因为 C++ 中
-1 % 3 = -1，而我们需要[0, k)范围内的非负余数，否则两个负数余数可能看似不同实则同余（例如-1和2都对 3 同余），使用(sum % k + k) % k可统一规范，保证配对正确。先查询后插入避免将当前元素构成的空子数组（长度为 0）计入结果。尤其当
k=1或余数为 0 时，若先插入再查询，r会与自身匹配，导致多算，因此必须先利用历史前缀和配对，再记录当前前缀。余数相同表示两个前缀和之差能被 K 整除，即中间连续子数组的和为 K 的倍数。记录出现次数可一次性累加所有匹配的历史前缀起点，高效统计。
含 0 时依然正确：
nums=[0,0],k=1，遍历：sum=0, r=0, 查 hash[0]=1 -> ret+1（子数组 [0]），插入0，hash[0]=2；第二个0同理，查 hash[0]=2 -> ret+2（子数组 [0] 和 [0,0]），总 ret=3，实际所有子数组和均为0，可被1整除，共3个，正确。
祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨
