免费企业模板网站,iis建立网站,免费开源cms网站源码,群晖 建wordpress 500974. 和可被 K 整除的子数组 - 力扣#xff08;LeetCode#xff09;
给定一个整数数组 nums 和一个整数 k #xff0c;返回其中元素之和可被 k 整除的非空 子数组 的数目。
子数组 是数组中 连续 的部分。 示例 1#xff1a;
输入#xff1a;nums [4,5,0,-2,-3,1], 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] 1042 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 % kk) % k 哈希表优化O(n) 时间解法
通过哈希表记录每个余数出现的次数只需一次遍历即可统计答案 初始化哈希表 放入 (0, 1)处理前缀和本身能被 k 整除的情况例如子数组从第一个元素开始。 动态计算余数 维护当前前缀和的余数 currentMod并修正为正值。 统计答案 若当前余数已存在于哈希表中则累加其出现次数。 更新哈希表 将当前余数的出现次数加 1。 代码实现
class Solution {public int subarraysDivByK(int[] nums, int k) {MapInteger, 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 种余数。 总结
通过结合前缀和、同余定理和哈希表我们高效地解决了子数组和整除问题。这种方法的精髓在于将问题转化为余数统计并利用哈希表快速查找历史记录。类似的思路还可以应用于其他子数组统计问题如和为某个值的子数组。
