Skip to content

Commit 7a132cd

Browse files
JavaCodeMingJavaCodeMing
committed
Create 974.和可被K整除的子数组(中等).md
1 parent 790e33e commit 7a132cd

1 file changed

Lines changed: 85 additions & 0 deletions

File tree

‎Algorithm/974.和可被K整除的子数组(中等).md‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
```text
2+
题目: 给定一个整数数组A,返回其中元素之和可被K整除的(连续、非空)子数组的数目;
3+
输入: A = [4,5,0,-2,-3,1], K = 5
4+
输出: 7
5+
解释: 有 7 个子数组满足其元素之和可被 K = 5 整除:
6+
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
7+
提示:
8+
1 <= A.length <= 30000
9+
-10000 <= A[i] <= 10000
10+
2 <= K <= 10000
11+
1.前缀和+哈希表+逐一统计:
12+
[1]思路:
13+
(1)pre(j)-pre(i)=nk;pre(i)表示前i项和,nk表示k的整数倍;
14+
(2)哈希表: key保存遍历到的值对K的正数模,value保存该正数模出现的次数;
15+
[2]实现:
16+
class Solution {
17+
public int subarraysDivByK(int[] A, int K) {
18+
// 计算子数组的个数
19+
int count = 0;
20+
// 定义一个变量保存加和后的值
21+
int pre = 0;
22+
// 哈希表的key保存遍历到的值对K的正数模,value保存key出现的次数
23+
Map<Integer, Integer> map = new HashMap<>();
24+
// 当前遍历值为K的整数倍时,需要计数加一
25+
map.put(0, 1);
26+
for (int value : A) {
27+
// 求前i项和
28+
pre += value;
29+
// 取正数模
30+
int module = (pre % K + K) % K;
31+
// 获取对K的正数模出现的次数,即存在符合条件的子数组的个数
32+
int temp = map.getOrDefault(module, 0);
33+
count += temp;
34+
// 将当前遍历到的值对K的正数模添加到哈希表
35+
map.put(module, temp + 1);
36+
}
37+
return count;
38+
}
39+
}
40+
[3]复杂度分析:
41+
(1)时间复杂度: O(n),其中n是数组A的长度;
42+
(2)空间复杂度: O(min(n,K)),即哈希表需要的空间;
43+
当N≤K时,最多有N个前缀和,因此哈希表中最多有N+1个键值对;
44+
当N>K时,最多有K个不同的余数,因此哈希表中最多有K个键值对;
45+
2.前缀和+哈希表+单次排列组合统计:
46+
[1]思路:
47+
(1)pre(j)-pre(i)=nk;pre(i)表示前i项和,nk表示k的整数倍;
48+
(2)哈希表: key保存遍历到的值对K的正数模,value保存该正数模出现的次数;
49+
(3)使用排列组合种类的计算公式计算:
50+
1)哈希表中的每个键值对(x,cx),它表示前缀和x(在模K的意义下)出现了cx次;
51+
2)相同x出现的位置两两之间都可构成可被K整除的连续子数组,数量为:cx(cx-1)/2
52+
[2]实现:
53+
class Solution {
54+
public int subarraysDivByK(int[] A, int K) {
55+
// 哈希表的key保存遍历到的值对K的正数模,value保存key出现的次数
56+
Map<Integer, Integer> map = new HashMap<>();
57+
// 当前遍历值为K的整数倍时,需要计数加一
58+
map.put(0, 1);
59+
// 定义一个变量保存加和后的值
60+
int pre = 0;
61+
// 遍历数组A
62+
for (int elem: A) {
63+
// 求前i项和
64+
pre += elem;
65+
// 取正数模
66+
int modulus = (pre % K + K) % K;
67+
// 将当前遍历到的值对K的正数模添加到哈希表
68+
map.put(modulus, map.getOrDefault(modulus, 0) + 1);
69+
}
70+
// 计算子数组的个数
71+
int count = 0;
72+
// 遍历哈希表
73+
for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
74+
// 排列组合个数公式: Cx(Cx-1)/2
75+
count += entry.getValue() * (entry.getValue() - 1) / 2;
76+
}
77+
return count;
78+
}
79+
}
80+
[3]复杂度分析:
81+
(1)时间复杂度: O(n),其中n是数组A的长度;
82+
(2)空间复杂度: O(min(n,K)),即哈希表需要的空间;
83+
当N≤K时,最多有N个前缀和,因此哈希表中最多有N+1个键值对;
84+
当N>K时,最多有K个不同的余数,因此哈希表中最多有K个键值对;
85+
```

0 commit comments

Comments
 (0)