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

974. 和可被 K 整除的子数组 - 力扣（LeetCode）

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。

子数组 是数组中 连续 的部分。

示例 1：

输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2:

输入: nums = [5], k = 9
输出: 0

提示:

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 104

暴力解法的问题

最直观的思路是枚举所有子数组，计算它们的和并检查是否能被 k 整除。但这种方法的时间复杂度为 ​O(n²)，当 n 达到 3e4 级别时会超时。我们需要一种更高效的方法。

优化思路：前缀和与同余定理

1. 前缀和与子数组的和

子数组 nums[i..j] 的和可以表示为前缀和的差值：

sum(i,j)=prefix[j]−prefix[i−1]

其中 prefix[j] 表示数组前 j 个元素的和。

2. 同余定理的应用

若两个前缀和的差值能被 k 整除，则它们的模 k 余数相同：

prefix[j]≡prefix[i−1] (mod k)⟹sum(i,j)≡0 (mod k)

因此，问题转化为：​寻找前缀和数组中余数相同的对数。

---

处理负数取模的细节

当数组中出现负数时，直接取模可能得到负余数。例如 -7 % 5 = -2，但实际余数应为 3（因为 -7 = 5*(-2) + 3）。我们需要统一修正余数为正数：

r=(r % k+k) % k

---

哈希表优化：O(n) 时间解法

通过哈希表记录每个余数出现的次数，只需一次遍历即可统计答案：

1. ​初始化哈希表：
   放入 (0, 1)，处理前缀和本身能被 k 整除的情况（例如子数组从第一个元素开始）。

2. ​动态计算余数：
   维护当前前缀和的余数 currentMod，并修正为正值。

3. ​统计答案：
   若当前余数已存在于哈希表中，则累加其出现次数。

4. ​更新哈希表：
   将当前余数的出现次数加 1。

---

代码实现

class Solution {public int subarraysDivByK(int[] nums, int k) {Map<Integer, Integer> modCount = new HashMap<>();modCount.put(0, 1); // 初始化：处理前缀和本身能被k整除的情况int currentMod = 0, count = 0;for (int num : nums) {currentMod = ((currentMod + num) % k + k) % k; // 计算当前余数（修正为正值）count += modCount.getOrDefault(currentMod, 0); // 累加相同余数的出现次数modCount.put(currentMod, modCount.getOrDefault(currentMod, 0) + 1); // 更新哈希表}return count;}
}

关键点解释

• ​**为什么初始化 map.put(0, 1)？**​
  假设前缀和 prefix[j] 的余数为 0，说明从数组开头到 j 的子数组满足条件。此时需要哈希表中预先存在 (0,1) 来统计这种情况。

• ​修正余数的必要性​
  确保所有余数在 [0, k-1] 范围内，避免负余数干扰统计。

• ​哈希表的作用​
  记录每个余数的历史出现次数，将时间复杂度从 O(n²) 优化到 O(n)。

---

复杂度分析

• ​时间复杂度：O(n)，只需一次遍历数组。
• ​空间复杂度：O(k)，哈希表最多存储 k 种余数。

---

总结

通过结合前缀和、同余定理和哈希表，我们高效地解决了子数组和整除问题。这种方法的精髓在于将问题转化为余数统计，并利用哈希表快速查找历史记录。类似的思路还可以应用于其他子数组统计问题（如和为某个值的子数组）。