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

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。

子数组 是数组中 连续 的部分。

示例 1:
输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2:
输入: nums = [5], k = 9
输出: 0

解题思路

输入：一个整数数组 nums 和一个整数 k

输出：返回其中元素之和可被 k 整除的非空子数组的数目。

本题属于哈希 + 前缀和问题。

我们假设 sum(i, j) % k == 0，那么 (preSum[j] - preSum[i - 1]) % k == 0，也就是说 preSum[j] % k == preSum[i - 1] % k

所以我们只需要找到当前前缀和是否与之前出现过的前缀和与 k 取模是否相等，如果相等就说明可以以 i 为起点 j 为终点构建一个子数组相加之和被 k 整除

我们可以用一个 哈希表 来记录之前出现过的前缀和与 k 取模的次数，每次计算出当前前缀和取模后的值后都和之前出现的次数配对就能得到答案

代码实现

python

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        preSum = 0       # 当前前缀和
        ans = 0          # 最终结果，统计满足条件的子数组个数

        modCount = {0: 1}  # 哈希表：记录每种余数出现的次数
                           # 初始为0表示空前缀，这样前缀和正好能被k整除的情况也能统计上

        for num in nums:
            preSum += num

            # 取模处理（注意处理负数的情况）
            mod = preSum % k
            if mod < 0:
                mod += k  # 确保余数是正的，防止负数出错

            # 如果当前余数在之前出现过，则说明存在子数组满足 sum % k == 0
            ans += modCount.get(mod, 0)

            # 更新当前余数出现的次数
            modCount[mod] = modCount.get(mod, 0) + 1

        return ans

javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraysDivByK = function(nums, k) {
    let ans = 0;
    let preSum = 0;
    const modCount = {0: 1};

    for (let num of nums) {
        preSum += num;
        let mod = preSum % k;
        if (mod < 0) mod += k;
        ans += modCount[mod] || 0;
        modCount[mod] = (modCount[mod] || 0) + 1;
    }

    return ans;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

930 国际版

930 中文版