wordpress 广告关闭,新塘网站seo优化,杭州市城市建设学校网站,做网站能不备案么题目
链接:leetcode链接 思路分析#xff08;前缀和 同余定理#xff09;
首先#xff0c;我们要了解一下什么是同余定理 同余定理#xff1a; 如果#xff08;a - b#xff09;/ p k …… 0 则 a % p b % p 证明我写在草稿纸上#xff0c;如下图#xff1a;
初…题目
链接:leetcode链接 思路分析前缀和 同余定理
首先我们要了解一下什么是同余定理 同余定理 如果a - b/ p k …… 0 则 a % p b % p 证明我写在草稿纸上如下图
初此之外我们还需要理解一个问题 在C/java中负数取模会怎么样呢 比如 - 2 % 5等于多少呢 按道理来说应该是3但是C/java里的答案是-2 这明显是需要进行修正的
如何进行修正呢 我们只需要 a % p p% p 这样无论是正数取模还是负数取模都不会出现问题。
OK到这里前置知识讲完了我们就正式开始讲思路了。
需要找一个子数组的和是k的倍数 那么只需要找两个区间的前缀和对k取模的余数相同即可。
和这道题的思路非常相似 传送门560.和为k的子数组 我们利用滚动数组去求前缀和 记录sum % k的余数 然后在[0,i-1]区间内去hash表中寻找一个区间的前缀和对k取模的结果与sum对k取模结果相同即可 将sum% k的余数放到hash表中一定要是先查找在插入 细节 1什么时候插入hash表 一定要是先查找在插入 2对于[0 , i]区间的和正好是K的倍数的情况如何处理 还是一样我们先去把余数0提前先往hash表里插一个即可 具体原因可以查看和为k的子数组这篇文章
代码
//同余定理int subarraysDivByK(vectorint nums, int k) {int sum 0,ret 0;unordered_mapint,int hash;//hash表里面放余数hash[0] 1;//这个0依旧是存的余数for(auto e:nums){sum e;int check (sum % k k) % k; // 对余数进行修正很关键if(hash.count(check)) ret hash[check]; hash[check];}return ret;}
