974. 和可被 K 整除的子数组 #34
Description
题目
给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
示例
示例 1:
输入：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]
解题
经典的前缀和问题
前缀和
- 数组 第 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]preSum[−1] 为 0，此时有：
A[0] +A[1]+…+A[j]=preSum[j]
按照题目转化 我们需要求出 (preSum[ j ] - preSum[ i - 1 ])mod K== 0 的状况，此时 [i, j] 这个数组就能满足需求
可能有点羞涩难懂，但是其实我们按照这样的思路就可以求出题目的结果
- 求出前缀和
- mod k 得出 余数
- 如果有其他的前缀和余数相同，表明两个前缀和之间的数组满足题解
- 可能会有多个前最和 mod k 余数相同
- 负数需要转换成正数（比如 k = 4，前缀和为 -1 和 3，看似前缀和不同，但是 前缀和的差值 3 - （-1）% 4 = 0，所以可以看作 -1 和 3 等价
- -1 mod k 不同语言可能得到不同的结果
解题方法
/**
* @param {number[]} A
* @param {number} K
* @return {number}
*/
var subarraysDivByK = function(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
};