0974. 和可被 K 整除的子数组【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 前缀和 + 哈希表

1. 📝 题目描述

• leetcode

给定一个整数数组 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

---

提示：

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• 2 <= k <= 10^4

2. 🎯 s.1 - 前缀和 + 哈希表

js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraysDivByK = function (nums, k) {
  const map = new Map()
  map.set(0, 1) // 前缀和为 0 的余数初始化为 1

  let prefixSum = 0
  let count = 0

  for (const num of nums) {
    prefixSum += num
    // 计算余数，注意处理负数情况
    let remainder = ((prefixSum % k) + k) % k

    // 如果之前出现过相同的余数，说明可以组成若干个子数组
    if (map.has(remainder)) {
      count += map.get(remainder)
    }

    // 更新余数出现次数
    map.set(remainder, (map.get(remainder) || 0) + 1)
  }

  return count
}

• 时间复杂度：$O(n)$，其中 n 是数组长度，只需遍历一次数组
• 空间复杂度：$O(min(n,k))$，哈希表最多存储 k 个不同的余数

算法思路：

• 同余定理应用：如果两个前缀和 prefixSum[i] 和 prefixSum[j] 对 k 同余，则子数组 nums[i+1...j] 的和能被 k 整除
• 前缀和计算：遍历数组累加前缀和，计算其对 k 的余数
• 负数余数处理：由于前缀和可能为负，使用 ((prefixSum % k) + k) % k 确保余数为非负
• 哈希表统计：用哈希表记录每个余数出现的次数，当前余数之前出现了 m 次，说明可以形成 m 个以当前位置结尾的子数组
• 初始化：map.set(0, 1) 表示前缀和为 0 的情况，用于处理从下标 0 开始的子数组
• 计数累加：每次遇到相同余数时，将之前出现的次数累加到结果中