Leetcode之974-和可被K整除的子数组(Subarray Sums Divisible by K)

算法题

题干

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

解法

  1. 暴力解法
  2. 同余解法, 与Leetcode之523-连续的子数组和很相似

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int subArraysDivByK(int[] A, int K) {
Map<Integer, Integer> map = new HashMap<>(16);
int sum = 0;
for (int ele : A) {
sum += ele;
sum %= K;
if (sum < 0) {
sum += K;
}
if (map.containsKey(sum)) {
map.put(sum, map.get(sum) + 1);
} else {
map.put(sum, 1);
}
}
int count = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int val = entry.getValue();
count += val * (val - 1) / 2;
if (entry.getKey() == 0) {
count += val;
}
}
return count;
}

代码解析

  1. 第2行代码新建HashMap, key为被K整除之后的正余数, value为个数。
  2. 第7-9行代码, 是将余数由负数转变为正数。
    • 比如sum%3余数范围是{-2,-1,0,1,2}, 转换之后范围是{0,1,2}。
    • 比如-9=(-2) * 4 + (-1), -1是余数。
    • 同时-9=(-3) * 4 + 3, 3也是余数, 这个3可以由余数-1加上除数4得到。
  3. 第19行代码表示相同余数的sum有val个, 那么每个余数对应有多少个子数组能被K整除。
    • 好比一条直线上N个不同的点,求线段的条数。
    • 解法就是C(N,2), 从N个点中取2个点的总取法。
  4. 第20-22行表示直接被K整除的情况。
如果有任何错误或疑问, 欢迎小伙伴们评论区留言^-^
( 完 )

欢迎各位看官关注

麻辣烫,走起
0%