海纳网站建设,商城前端模板,西安给大学做网站公司,动画网站源码大家好#xff0c;我是晴天学长#xff0c;同余定理的应用#xff0c;需要的小伙伴可以关注支持一下哦#xff01;后续会继续更新的。 1) .和可被 K 整除的子数组 题目描述
给定一个整数数组 A#xff0c;返回其中元素之和可被 K 整除的#xff08;连续、非空#xff0…大家好我是晴天学长同余定理的应用需要的小伙伴可以关注支持一下哦后续会继续更新的。 1) .和可被 K 整除的子数组 题目描述
给定一个整数数组 A返回其中元素之和可被 K 整除的连续、非空子数组的数目。
示例
输入A [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 2) .算法思路
前缀和HashMap
解析:
我们需要求出满足条件的区间见下图 我们需要找到满足和为 K 的区间。我们此时 presum 是已知的k 也是已知的我们只需要找到 presum - k区间的个数就能得到 k 的区间个数。但是我们在当前题目中应该怎么做呢见下图。 我们在之前的例子中说到presum[j1] - presum[i] 可以得到 nums[i] nums[i1]… nums[j]也就是[i,j]区间的和。
那么我们想要判断区间 [i,j] 的和是否能整除 K也就是上图中紫色那一段是否能整除 K那么我们只需判断
(presum[j1] - presum[i] ) % k 是否等于 0 即可
我们假设 (presum[j1] - presum[i] ) % k 0则
presum[j1] % k - presum[i] % k 0;
presum[j 1] % k presum[i] % k ;
我们 presum[j 1] % k 的值 key 是已知的则是当前的 presum 和 k 的关系我们只需要知道之前的前缀区间里含有相同余数 key的个数。则能够知道当前能够整除 K 的区间个数。见下图 我们看到上面代码中有一段代码是这样的 int key (presum % K K) % K; 这是为什么呢不能直接用 presum % k 吗
这是因为当我们 presum 为负数时需要对其纠正。纠正前(-1) %2 (-1)纠正之后 ( (-1) % 2 2) % 21 保存在哈希表中的则为 1.则不会漏掉部分情况例如输入为 [-1,2,9],K 2如果不对其纠正则会漏掉区间 [2] 此时 2 % 2 0符合条件但是不会被计数。
那么这个题目我们可不可以用数组代替 map 呢当然也是可以的因为此时我们的哈希表存的是余数余数最大也只不过是 K-1所以我们可以用固定长度 K 的数组来模拟哈希表。 3) .算法步骤
1.创建一个HashMap对象 map 用于存储余数与对应出现次数的映射关系。 2.初始化变量 PerSum 为0表示当前位置的前缀和。 3.初始化变量 answer 为0表示满足条件的子数组个数。 4.将余数为0的初始情况放入 map 中即前缀和为0的情况出现次数为1。 5.使用一个循环遍历数组中的元素。 6.将当前元素的值累加到 PerSum 中即计算当前位置的前缀和。 7.使用同余定理计算当前前缀和除以k的余数由于负数取模的结果可能为负数为8.确保结果为非负整数需要进行加k再取模的操作。 9.检查 map 中是否包含当前余数如果是则将对应的出现次数加到 answer 中。 10.将当前余数和对应的出现次数放入 map 中更新映射关系。 11.循环结束后返回 answer表示满足条件的子数组个数。 4.代码示例
class Solution {public int subarraysDivByK(int[] nums, int k) {MapInteger, Integer map new HashMapInteger, Integer();long PerSum 0;int answer 0;map.put(0, 1);for (int i 0; i nums.length; i) {PerSum nums[i];// 同余定理因为不符合分配律int mod (int) ((PerSum%kk)%k);if (map.containsKey(mod)) {answermap.get(mod);}map.put(mod, map.getOrDefault(mod, 0) 1);}return answer;}
}5.总结
同余定理的运用。 试题链接
