Skip to main content

和可被-k-整除的子数组

Tips

题目类型: 前缀和

相关题目:

题目​

给定一个整数数组 A, 返回其中元素之和可被 K 整除的(连续, 非空)子数组的数目.

示例

输入: A = [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]

题解​

这道跟 560. 和为 k 的子数组 如出一辙, 需要注意的是 const key = ((preSum % K) + K) % K, 这是要保证余数不能为负数.

/**
 * @param {number[]} A
 * @param {number} K
 * @return {number}
 */
var subarraysDivByK = function (A, K) {
  const len = A.length
  const map = new Map([[0, 1]])
  let preSum = 0
  let count = 0

  for (let i = 0; i < len; i++) {
    preSum += A[i]
    const key = ((preSum % K) + K) % K
    if (map.has(key)) {
      count += map.get(key)
    }

    if (map.has(key)) {
      map.set(key, map.get(key) + 1)
    } else {
      map.set(key, 1)
    }
  }

  return count
}