【前缀和】974. 和可被 K 整除的子数组

Halo，这里是Ppeua。平时主要更新C++，数据结构算法，Linux与ROS…感兴趣就关注我bua！

题目:

示例:

题解:

本题与560.和为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;
}
};