和可被k整除的子数组问题

和可被k整除的子数组问题

leetcode链接：. - 力扣（LeetCode）

思路：前缀和第二种表示方式即循环列出方式+同余定理+取模修正：

还是通过循环把它分为由0到i的位置一次由i位置往前走去组合，即可以得到所有的情况，因此要判断x%k=0即转化为（sum-前缀和）%k成立即可 即由同余定理——>

满足sum%k=前缀和%k 通俗一点也就是通过for循环每次遍历前缀和（sumi之前的sum）都放入了hash，当遍历到i位置，只需要判断hash中是否对应sum%k下标是否存在值即可

注意：存在负数和0，不能用滑动窗口。

三·代码：

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int sum=0,ret=0;
         unordered_map<int,int> hash;
        hash[0%k]=1;//特殊情况，这如果恰好x为此时的sumi那么对应的就是前缀和为0，即若它是，则此时hash【0】必然有数即初始化为1；
      
           for(auto a:nums){
              sum+=a;
              int remainder=(sum%k+k)%k;//这里进行了修正处理原因是如果余数出现负数，则可能会有情况不符合如：【-1,2,9】，k=2这里
              //2是一个子数组，但是sum加到2，此时余数是1，而hash没有对应1的下标只有-1（-1%2）故这时可以通过修正把它变为1
              if((remainder)) ret+=hash[remainder];//上下顺序不能颠倒，如果颠倒则无论如何这个if肯定为真
              hash[remainder]++;
           }
           return ret;
    }
};