Leet code 974 和可被K整除的子数组

解题思路  同余必定符合条件

我们计算出从第一个位置到后面每个位置的sum

如果给出一段数组nums为 3  4  7  3   k=5

第一个位置sum=3  第二位置sum=7  第三个位置sum=14  第四个位置sum=17

这里7和17余数都为2  17-7=10  10%5=0   这里可以看出余数相同一定之间有解

我们根据思路可以建立 map<int,int> hash  第一个位置存  ((sum%k)+k) % k

为什么要这样写 因为sum可能是负数 这样会影响后续的结果 必须存余数的绝对值

第二个位置存sum的个数 

核心代码

for(int x:nums)

       {

         sum =sum+x;

         div= ((sum%k)+k) % k ;

         if(hash.count(div))  ret + =hash[div]; //存结果

         hash[div]++;

       }

注意   hash[0] = 1  第一个被 k 模为 0 的 sum 需要直接进入if条件加载到结果中 

为什么hash[ div ] ++   

假如数组为5  6  4  数组第一个sum的取余是0  ret + =hash[div]  那么结果就是 子数组5 

hash[div]++ 是为了后续满足条件的sum和前面的数相拼接  第二次拼接子数组为 5 6 4 或者 6 4 这里就有两个 ret就需要+=2 

对于余数不为0的sum  如果有两个以上就可以拼接 所以对于余数不为0的sum

hash都初始化为0    比如sum 6  和  11  都余 1 那么肯定可以拼接 而且ret只+1  

代码如下

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
       unordered_map<int,int> hash;
       int sum=0;
       int ret=0;
       int div;
       hash[0]=1;//万一第一个数被K取余为0 也要算入
       for(int x:nums)
       {
         sum =sum+x;
          div= ((sum%k)+k) % k ;
         if(hash.count(div)) ret+=hash[div];
         hash[div]++;
       }
       return ret;
    }
};