前缀和解子数组计数：和为 K 与可被 K 整除

30. 和可被 k 整除的子数组

题目链接：

974. 和可被 K 整除的子数组 - 力扣（LeetCode）

题目描述：

给定一个整数数组 nums 和一个整数 k，返回满足'子数组元素和能被 k 整除'的非空连续子数组数量。

题目示例：

输入：nums = [4,5,0,-2,-3,1], k = 5 输出：7 解释：共有 7 个子数组满足条件。

前缀和 + 同余 + 哈希表

这题和上一题几乎是同一套思路，只是把'相等'换成了'同余'。

如果两个前缀和 a 和 b 满足 (a - b) % k == 0，那它们对 k 取模的结果相同。换句话说，只要两个前缀和的余数一样，它们之间夹着的那段子数组和就能被 k 整除。

设 sum[i] 是当前位置的前缀和，那么我们只要统计：在当前位置之前，有多少个前缀和的余数和 sum[i] % k 相同。

这里要额外处理负数取模。C++ 里 -1 % 3 会得到 -1，不是我们想要的 2。所以通常写成 (sum % k + k) % k，把结果压回到 [0, k-1] 区间。这个写法不优雅，但很稳，线上题里够用了。

前缀和解法代码（C++）

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        hash[0 % k] = 1; // 0 这个数的余数
        int sum = 0, ret = 0;
        for(auto x : nums) {
            sum += x; // 算出当前位置的前缀和
            int r = (sum % k + k) % k;
            if(hash.count(r)) ret += hash[r];
            hash[r]++;
        }
        return ret;
    }
};

小结

这两题都在数'前缀和之间的关系'。一题是差值等于 k，一题是余数相同。前缀和负责把区间和转成两个前缀的关系，哈希表负责把查询从 O(n) 压到 O(1)。思路不花哨，但很实用，尤其适合这种'统计满足条件的子数组个数'的题。