安阳网站建设_,建筑业企业所得税2%,成都网站游戏设计,wordpress缩进columnHalo#xff0c;这里是Ppeua。平时主要更新C#xff0c;数据结构算法#xff0c;Linux与ROS…感兴趣就关注我bua#xff01; 974. 和可被 K 整除的子数组 题目:示例:题解: 题目: 示例: 题解:
本题与560.和为K的子数组高度相似
同样的,本题利用了前缀和的定理.当(pre[i]-… Halo这里是Ppeua。平时主要更新C数据结构算法Linux与ROS…感兴趣就关注我bua 974. 和可被 K 整除的子数组 题目:示例:题解: 题目: 示例: 题解:
本题与560.和为K的子数组高度相似
同样的,本题利用了前缀和的定理.当(pre[i]-pre[j-1])mod k0时.即为所寻找的答案.
将这个式子做简单的变换.则可以得到.pre[i] mod k pre[j-1] mod k时即为所寻找的答案.
同样利用hash存储每一次答案.
最后的答案即为以每一个位置为数尾的符合条件的子数组个数之和。需要注意的一个边界条件是我们需要对哈希表初始化记录mp[0]1的情况这样就考虑了前缀和本身被 k 整除的情况。
由于C没有对负数取模的操作,所以我们需要对负数的模进行处理,具体的如下:
(sum%k)的结果可能为负数,此时进行如下处理(sum%kk)%k,
即使是远小于K的负数其对K同余后其负数同余值的绝对值都要小于K所以加上K后再对K同余就是其正数的同余值.
举个例子:
(-33%55)%52
代码:
class Solution {
public:int subarraysDivByK(vectorint nums, int k) {for(int i1;inums.size();i){nums[i]nums[i-1];}unordered_mapint,intmap;map[0]1;int res0;for(int i0;inums.size();i){int models((nums[i]%kk)%k);if(map.find(models)!map.end()){resmap[models];}map[models];}return res;}
};class Solution { public: int subarraysDivByK(vector nums, int k) { for(int i1;inums.size();i) { nums[i]nums[i-1]; } unordered_mapint,intmap; map[0]1; int res0; for(int i0;inums.size();i) { int models((nums[i]%kk)%k); if(map.find(models)!map.end()) { resmap[models]; } map[models]; } return res; } };
