原文链接: https://leetcode-cn.com/problems/subarray-sums-divisible-by-k

英文原文

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Example 2:

Input: nums = [5], k = 9
Output: 0

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 104

中文题目

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

 

提示：

1. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 2 <= K <= 10000

通过代码

高赞题解

什么是前缀和

• 定义：数组 第 0 项 到 当前项 的和。用一个数组 preSum 表示：

$$preSum[i] = A[0] + A[1] +…+A[i]$$

• 数组第 i 项可以表示为相邻前缀和之差：

$$A[i] = preSum[i] - preSum[i - 1]$$

• 多项叠加，有：

$$A[i] +…+A[j]=preSum[j] - preSum[i - 1]$$

• i 可以为 0，此时 i - 1 为 - 1，我们故意让 $preSum[-1]$ 为 0，此时有：

$$A[0] +A[1]+…+A[j]=preSum[j]$$

• 设置这种荒谬的情况，只是为了让边界情况的计算也能套用上面的通式。

题目等价转化

• 子数组的元素之和 => $A[i]$ 到 $A[j]$ 的和

• 元素和能被 K 整除的子数组数目 => 有几种$i、j$组合，使得$A[i]$到$A[j]$之和 mod K == 0

  ↓ ↓ ↓ 转化为 ↓ ↓ ↓

• 有几种 $i、j$ 组合，满足 $(preSum[ j ] - preSum[ i - 1 ])$ mod $K== 0$。

• 有几种 $i、j$ 组合，满足 $preSum[j]$ mod $K$ == $preSum[i-1]$ mod $K$。

  • 前提：$preSum[j]$ 、$preSum[i-1]$ 为正整数。负数的情况要处理。

前缀和怎么求

• 数组当前项的前缀和 = 上一项的前缀和 + 数组当前项

• 我们可以求出数组 A 每一项的前缀和，让它 mod K，mod 完再看哪两项相等，去计数。

• 但前面通式有$i、j$两个变量，找出所有相等的两项，需要两层循环，能否优化？

我们只关心：数值和出现次数

• 数组A的元素都有自己的前缀和，但我们不关心前缀和对应了哪一项。我们只关心出现过哪些「前缀和 mod K」的值，以及出现这个值的次数。

• 用一个变量 preSumModK，将每次求出的「前缀和 mod K」，存入哈希表：

  • key：前缀和 mod K

  • value：这个值出现的次数

• 「前缀和 mod K」值恰好是 0,1,2…,K-1，正好和索引对应，所以也可以用数组去存。

找到 preSumModK 的递推关系，用于迭代计算

• 模的分配率： (a + b) mod c = (a mod c + b mod c) mod c

• 当前的 preSumModK

  = $($ 当前的前缀和 $)$ mod $K$

  = $($ 上一项的前缀和 $+$ $A[i]$ $)$ mod $K$

  = $( ($上一项的前缀和) mod $K$ $+$ $A[i]$ mod $K$ $)$ mod $K$

  = $($ 上一个 preSumModK $+$ $A[i]$ mod $K$ $)$ mod $K$

  = $($ 上一个 preSumModK $+$ $A[i]$ $)$ mod $K$

• 前后的 preSumModK 有了递推关系，可以在迭代中计算。

整个流程

• 预置 preSum[-1] = 0

  • 遍历数组 A 之前，map 提前放入 0:1 键值对，代表求第 0 项前缀和之前，前缀和 mod K 等于 0 这种情况出现了 1 次。

• 遍历数组 A，求当前项的 preSumModK ，存入 map 中：

  • 之前没有存过，则作为 key 存入，value 为 1。

  • 之前存过了，则 value 加 1。

• 边存边查看，如果 map 中已经存在 key 等于当前的 preSumModK：

  • 说明存在之前求过的 preSumModK 等于 当前 preSumModK，把 key 对应的出现次数，累加给 count。

  • 过去的这个前缀，与当前的前缀，差分出一个子数组，过去的这个前缀和出现过几次 ，就是有几个过去的前缀，与当前前缀，差分出几个满足条件的子数组。

尝试一句话概括

• 根据当前前缀和 mod K，在哈希表中找到与之相等的 key。满足条件的 历史preSumModK 出现过 n 次，就是当前前缀和 能找到 n 个历史前缀和，与之形成 n 个不同的子数组，满足元素和能被 K 整除。

• 遍历数组 A 每一项，做以上步骤，n 不断累加给 count，最后返回 count。

复杂度

Time：O(n)

Space：O(K)。 mod 的结果最多 K 种，哈希表最多存放 K 个键值对

补充：前缀和 为负数 的情况

• 拿K = 4为例，求出某个前缀和为 -1，-1 % K 应该为 3，但有的编程语言 -1 % K = -1

• 这个 -1，要加上 K，转成正 3。为什么 preSum 值为 -1 和 3 需要归为同一类？因为：

• -1 和 3 分别模 4 的结果看似不相等，但前缀和之差：3-(-1) 等于 4。4 % K = 0，即所形成的子数组满足元素和被 4 整除。所以前缀和 -1 和 3 其实是等价的。

代码

[]

const subarraysDivByK = (A, K) => {

  let preSumModK = 0;

  let count = 0;

  const map = { 0: 1 };

  for (let i = 0; i < A.length; i++) {

    preSumModK = (preSumModK + A[i]) % K; // 递推式子

    if (preSumModK < 0) {

      preSumModK += K;

    }

    if (map[preSumModK]) {      // 已经存在于map

      count += map[preSumModK]; // 把对应的次数累加给count

      map[preSumModK]++;        // 并且更新出现次数，次数+1

    } else {

      map[preSumModK] = 1;      // 之前没出现过，初始化值为1

    }

  }

  return count;

};

[]

func subarraysDivByK(A []int, K int) int {

	preSumModK := 0

	count := 0

	hash := map[int]int{0: 1}



	for i := 0; i < len(A); i++ {

		preSumModK = (preSumModK + A[i]) % K

		if preSumModK < 0 {

			preSumModK += K

		}

		if v, ok := hash[preSumModK]; ok {

			count += v

			hash[preSumModK]++

		} else {

			hash[preSumModK] = 1

		}

	}

	return count

}

代码2：用数组代替哈希表存mod

[]

const subarraysDivByK = (A, K) => {

  let preSumModK = 0;

  let count = 0;

  const map = new Array(K).fill(0);

  map[0] = 1;

  for (let i = 0; i < A.length; i++) {

    preSumModK = (preSumModK + A[i]) % K;

    if (preSumModK < 0) {

      preSumModK += K;

    }

    count += map[preSumModK]; // 索引对应模的结果，值对应出现次数

    map[preSumModK]++;

  }

  return count;

};

[]

func subarraysDivByK(A []int, K int) int {

	preSumModK := 0

	count := 0

	hash := make([]int, K)

	hash[0] = 1



	for i := 0; i < len(A); i++ {

		preSumModK = (preSumModK + A[i]) % K

		if preSumModK < 0 {

			preSumModK += K

		}

		count += hash[preSumModK]

		hash[preSumModK]++

	}

	return count

}

前前后后改了几十遍，应该很流畅好懂了，如果有帮助，点个赞鼓励我继续写下去，关注我，我们一起爆破算法题。

最后修改于：2021-08-31

统计信息

通过次数	提交次数	AC比率
39045	83713	46.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
和为 K 的子数组	中等