Keshawn_lu's Blog

Leetcode 974. 和可被 K 整除的子数组

字数统计: 498阅读时长: 2 min
2020/05/27 Share

题目简介:

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

示例:

1
2
3
4
5
输入: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

思路:

使用前缀和的思想,sum[i]代表以i为结尾的前缀和,若数组[i, ……, j]元素之和能被 K 整除,则(sum[j] - sum[i - 1]) % K == 0,根据同余定理,可以得到sum[j] % K == sum[i - 1] % K,所以我们将每次数组元素和除 K 的余数存入哈希表,并在遍历时判断之前有没有相同的余数,若有,则中间的一段数组便满足要求。

因为C++取模时,当被除数为负数时取模结果为负数(如 -1 % 2 == -1, 但是2 == -1 * -1 + 1,所以正确结果为1),所以求余数时需要用(sum % K + K) % K的形式。

相当于给所有的前缀和一个偏移量 K,正数取模不变,负数取模变成 K 加这个负数。

tips:

  • 哈希表中余数为0需赋初值1,例如sum = 3, K = 3, sum % K == 0,如果不赋初值,则这个数组无法被统计到。

  • 前缀和:一个数组的某项下标之前(包括此项元素)的所有数组元素的和。

  • 同余定理:如果两个整数的差(a-b)能被m整除,那么a,b对m同余,即余数相同。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int subarraysDivByK(vector<int>& A, int K) {

unordered_map<int, int> record = {{0, 1}};

int sum = 0;
int count = 0;
for(int i = 0; i < A.size(); i++){

sum += A[i];
int mod_res = (sum % K + K) % K; //防止sum为负数时出错

if(record.count(mod_res)){
count += record[mod_res];
}

record[mod_res]++;
}

return count;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: