当前位置：首页 > news >正文

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

news 2025/9/4 12:27:41

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) 时间解法

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

初始化哈希表：
放入 (0, 1)，处理前缀和本身能被 k 整除的情况（例如子数组从第一个元素开始）。
动态计算余数：
维护当前前缀和的余数 currentMod，并修正为正值。
统计答案：
若当前余数已存在于哈希表中，则累加其出现次数。
更新哈希表：
将当前余数的出现次数加 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)。