欢迎阅读 欢迎来到「和可被 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)保证哈希键统一。查询配对若哈希表存在余数rret hash[r]与之前同余的前缀和每个都配对成一个子数组。记录当前hash[r]先查后插保证子数组非空。返回遍历结束返回ret。 示例nums [4, 5, 0, -2, -3, 1]k 5步骤sumr (sum%55)%5查询 hash[r]hash 变化ret初始化0——{0:1}0i0, x444查 4无{0:1, 4:1}0i1, x594查 4 →1{0:1, 4:2}1i2, x094查 4 →2{0:1, 4:3}3i3, x-272查 2无{0:1, 4:3, 2:1}3i4, x-344查 4 →3{0:1, 4:4, 2:1}6i5, x150查 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 5sum[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 -3k 5C 中-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(vectorint nums, int k) { unordered_mapint, 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或漏掉第二遍都会让键不一致同余配对错乱。难点3hash[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],k1验证。如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案hash[0]1表示空前缀余数为 0 出现过一次用于处理从数组开头下标 0开始的子数组。例如nums[4,5],k3前缀和依次为 4,9余数分别为 1,0当遍历到第二个元素时r0查询hash[0]命中来自空前缀计数 1对应子数组[4,5]和为 9 可被 3 整除若不存 0 则漏计。必须修正负数取模因为 C 中-1 % 3 -1而我们需要[0, k)范围内的非负余数否则两个负数余数可能看似不同实则同余例如-1和2都对 3 同余使用(sum % k k) % k可统一规范保证配对正确。先查询后插入避免将当前元素构成的空子数组长度为 0计入结果。尤其当k1或余数为 0 时若先插入再查询r会与自身匹配导致多算因此必须先利用历史前缀和配对再记录当前前缀。余数相同表示两个前缀和之差能被 K 整除即中间连续子数组的和为 K 的倍数。记录出现次数可一次性累加所有匹配的历史前缀起点高效统计。含 0 时依然正确nums[0,0],k1遍历sum0, r0, 查 hash[0]1 - ret1子数组 [0]插入0hash[0]2第二个0同理查 hash[0]2 - ret2子数组 [0] 和 [0,0]总 ret3实际所有子数组和均为0可被1整除共3个正确。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨
LeetCode 974：和可被 K 整除的子数组（前缀和） —— 题解
欢迎阅读 欢迎来到「和可被 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)保证哈希键统一。查询配对若哈希表存在余数rret hash[r]与之前同余的前缀和每个都配对成一个子数组。记录当前hash[r]先查后插保证子数组非空。返回遍历结束返回ret。 示例nums [4, 5, 0, -2, -3, 1]k 5步骤sumr (sum%55)%5查询 hash[r]hash 变化ret初始化0——{0:1}0i0, x444查 4无{0:1, 4:1}0i1, x594查 4 →1{0:1, 4:2}1i2, x094查 4 →2{0:1, 4:3}3i3, x-272查 2无{0:1, 4:3, 2:1}3i4, x-344查 4 →3{0:1, 4:4, 2:1}6i5, x150查 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 5sum[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 -3k 5C 中-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(vectorint nums, int k) { unordered_mapint, 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或漏掉第二遍都会让键不一致同余配对错乱。难点3hash[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],k1验证。如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案hash[0]1表示空前缀余数为 0 出现过一次用于处理从数组开头下标 0开始的子数组。例如nums[4,5],k3前缀和依次为 4,9余数分别为 1,0当遍历到第二个元素时r0查询hash[0]命中来自空前缀计数 1对应子数组[4,5]和为 9 可被 3 整除若不存 0 则漏计。必须修正负数取模因为 C 中-1 % 3 -1而我们需要[0, k)范围内的非负余数否则两个负数余数可能看似不同实则同余例如-1和2都对 3 同余使用(sum % k k) % k可统一规范保证配对正确。先查询后插入避免将当前元素构成的空子数组长度为 0计入结果。尤其当k1或余数为 0 时若先插入再查询r会与自身匹配导致多算因此必须先利用历史前缀和配对再记录当前前缀。余数相同表示两个前缀和之差能被 K 整除即中间连续子数组的和为 K 的倍数。记录出现次数可一次性累加所有匹配的历史前缀起点高效统计。含 0 时依然正确nums[0,0],k1遍历sum0, r0, 查 hash[0]1 - ret1子数组 [0]插入0hash[0]2第二个0同理查 hash[0]2 - ret2子数组 [0] 和 [0,0]总 ret3实际所有子数组和均为0可被1整除共3个正确。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨