电商网站 解决方案,广州市网站建设 乾图信息科技,怎么样做长久的电影网站,金华做网站最专业的公司前言
1.前缀和哈希表#xff08;排列组合思想#xff09;
2.同余定理 3.Cpp和Java修正【负数%正数】
#xff08;num%k k#xff09;% k
题目解析
和可被K整除的子数组#xff1a;
给定一个整数数组 nums 和一个整数 k #xff0c;返回其中元素之和可被 k 整除的非…前言
1.前缀和哈希表排列组合思想
2.同余定理 3.Cpp和Java修正【负数%正数】
num%k k% k
题目解析
和可被K整除的子数组
给定一个整数数组 nums 和一个整数 k 返回其中元素之和可被 k 整除的非空 子数组 的数目。
子数组 是数组中 连续 的部分。 本题在leetcode560“和为K的子数组”这道题上进行了扩展
但同样是--统计一段和满足某条件的连续区间子数组的数目。
算法原理
暴力解法
用两层循环遍历所有子数组的情况求和看是否满足条件。
虽然容易想但并非毫无意义在想暴力解法的过程中我们会发现题目所给数组包含负数和0不具有单调性因此不能用双指针“滑动窗口”进行优化。那怎么办 前缀和哈希表
在学完前缀和以后每当看到题目要求连续区间的和时都应该想到前缀和毕竟在有了前缀和之后求某段区间的和都只需要O(1)就能完成。
那么如何用前缀和优化又是个问题。
为了使用前缀和首先要一改暴力解法的思想以i位置为起点遍历所有子数组。、这样我们只能求出后缀和与前缀和完全不搭边。
那么反过来想遍历以i位置为结尾的子数组似乎就好起来了既能考虑所有子数组的情况又能使用前缀和。当有了i位置的前缀和之和其实就不需要再一个一个遍历子数组的情况了。
因为sum[i,j] prefix_sum[j] - prefix[i]。有了两个前缀和就能够算出这两段前缀和之间的值。图中抽象表示未处理细节
在知道要使用前缀和的情况下再观察一下题目要求和可被K整除的子数组。
子数组不就是sum[i,j] prefix_sum[j] - prefix[i]这个嘛。且和能够用前缀和之差表示再结合同余定理就会发现找到 j 位置时只要前面 j 前有 i 位置满足二者的前缀和(mod)k相等就能推出sum[i,j]这段子数组之和能被K整除只需要把下面的逻辑逆着推上来即可。 这样用哈希表记录下某位置之前的前缀和结合哈希表快速查找的特性
就可以在到 i 位置时 查找之前满足条件的前缀和出现的次数就是满足条件的子数组的个数。
哈希中可以只存前缀和模K的余数及其出现的次数
注意的细节就是哈希表需要初始化map[0] 1。这是因为可能某位置的前缀和就刚好满足条件那么子数组就是该段前缀和减去一个0需要在哈希表中找到一个为0的前缀和。换种理解就是index在-1位置时前缀和为0。
还有数组中存在负数对于取模操作Cpp 和Java 的 [ 负数%正数 负数 ]
可是对K取模运算余数的范围是[0,K-1]是正数就需要特殊处理。
对负数num % k k 但正数不需要啊
有一个正负取模统一表达式num%k k% k; 就行了。
代码实现
不需要真的创建一个数组存前缀和都放到哈希表中即可。
int subarraysDivByK(vectorint nums, int k) {int n nums.size(), sum 0, ct 0;unordered_mapint, int m;m[0];for (int e : nums) {sum e;ct m[(sum % k k) % k];m[(sum % k k) % k];}return ct;}
还有一种排列组合的思路把前缀和模K都求出后放入哈希相同的余数两两进行排列组合也是满足条件的子数组。
int subarraysDivByK(vectorint nums, int k) {int n nums.size(), sum 0, ct 0;unordered_mapint, int m;m[0];for(int e : nums){sume;m[(sum%kk)%k];}for(auto [k,v] : m){ct v*(v-1)/2;}return ct;}
