Halo，这里是Ppeua。平时主要更新C++，数据结构算法，Linux与ROS…感兴趣就关注我bua！
974. 和可被 K 整除的子数组
题目:
示例:
题解:
同样的,本题利用了前缀和的定理.当(pre[i]-pre[j-1])mod k==0时.即为所寻找的答案.
将这个式子做简单的变换.则可以得到.pre[i] mod k ==pre[j-1] mod k时即为所寻找的答案.
同样利用hash存储每一次答案.
最后的答案即为以每一个位置为数尾的符合条件的子数组个数之和。需要注意的一个边界条件是，我们需要对哈希表初始化，记录mp[0]=1的情况，这样就考虑了前缀和本身被 k 整除的情况。
由于C++没有对负数取模的操作,所以我们需要对负数的模进行处理,具体的如下:
(sum%k)的结果可能为负数,此时进行如下处理(sum%k+k)%k,
即使是远小于K的负数，其对K同余后，其负数同余值的绝对值都要小于K，所以加上K后再对K同余就是其正数的同余值.
举个例子:
(-33%5+5)%5=2
代码:
class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { for(int i=1;i<nums.size();i++) { nums[i]+=nums[i-1]; } unordered_map<int,int>map; map[0]=1; int res=0; for(int i=0;i<nums.size();i++) { int models=((nums[i]%k+k)%k); if(map.find(models)!=map.end()) { res+=map[models]; } map[models]++; } return res; } };
class Solution { public: int subarraysDivByK(vector& nums, int k) { for(int i=1;i<nums.size();i++) { nums[i]+=nums[i-1]; } unordered_map<int,int>map; map[0]=1; int res=0; for(int i=0;i<nums.size();i++) { int models=((nums[i]%k+k)%k); if(map.find(models)!=map.end()) { res+=map[models]; } map[models]++; } return res; } };
