【前缀合】Leetcode 和可被 K 整除的子数组

题目解析

974. 和可被 K 整除的子数组

算法讲解

前置知识点：

1. 同余定理：(a+b) % c == 0 可以得出 a % c == b % c
2. C++中负数求余的结果是负数，但是本题需要的是正数，所以我们为了修正这个结果，需要进行(负数 % 正数 + 正数) % 正数

0~i这一段区间是sum，为了寻找一段区间能够被k整除，所以看一下(sum - x) % k是否能被整除，由同余定理得出：sum % k == x % k，因此我们只需要寻找这一段区间中有几个余数等于sum % k的属于需要将负数取余情况代入

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int sum = 0;
        unordered_map<int,int>Hash;
        int ret = 0;
        Hash[0 % k]++;
        for(auto n : nums)
        {
            sum += n; //计算当前位置的前缀和
            int r = (sum % k + k) % k;//修正结果
            if(Hash.count(r))ret += Hash[r];  //当前这一段区间有多少个前缀和的余数等于sum % k
            Hash[r]++;
        }
        return ret;
    }
};