Skip to main content

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

Date：2022-03-13 16:19:40

标签：

  • 前缀和

题目：974.和可被 K 整除的子数组 ( 中等😕 )​

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

分析​

  • 暴力法 + 哈希表

    双层循环，哈希表中存之前的和，依次判断与 k 的余数，如果为 0，则为答案，将答案累加即可

    • 时间复杂度 O(n^2)，空间复杂度 O(n)

  • 前缀和 + 逐一统计

    这是 LeetCode 的一段重要的阶梯思路：

    image-20220311064454351

    • 问题一：为什么要将 负余数 纠正呢？(sum % k + k) % k 纠正算法又是怎么来的呢？

    • 时间复杂度 O(n)，空间复杂度 O(n)

题解​

function subarrayDivByK(nums: number[], k: number): number {
  const len = nums.length
  const map = new Map<number, number>()

  map.set(0, 1)

  let sum = 0,
    ans = 0
  for (let i = 0; i < len; ++i) {
    sum += nums[i]

    let mod = ((sum % k) + k) % k
    // mod = mod < 0 ? -mod : mod

    const same = map.get(mod) ?? 0

    ans += same

    map.set(mod, same + 1)
  }

  return ans
}

使用

function main() {
  const nums = [4, 5, 0, -2, -3, 1]
  const k = 5

  console.log('[]:', subarrayDivByK(nums, k))
}
main()

export {}

问题解答​

问题一：为什么要将 负余数 纠正呢？(sum % k + k) % k 纠正算法又是怎么来的呢？

因为余数不应该为负数，-1 和 1 与 2 的余数是一致的，都为 1