友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
992. Subarrays with K Different Integers
Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.
(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)
Return the number of good subarrays of A.
Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].Note:
-
1 ⇐ A.length ⇐ 20000 -
1 ⇐ A[i] ⇐ A.length -
1 ⇐ K ⇐ A.length
参考资料
Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.
(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)
Return the number of good subarrays of A.
Example 1:
Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].Example 2:
Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].Note:
-
1 ⇐ A.length ⇐ 20000 -
1 ⇐ A[i] ⇐ A.length -
1 ⇐ K ⇐ A.length
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**
* Runtime: 5 ms, faster than 93.74% of Java online submissions for Subarrays with K Different Integers.
* Memory Usage: 51.9 MB, less than 5.26% of Java online submissions for Subarrays with K Different Integers.
*
* Copy from: https://mp.weixin.qq.com/s/6YeZUCYj5ft-OGa85sQegw[面试官，你再问我滑动窗口问题试试？我有解题模板，不怕！]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-30 19:44
*/
public int subarraysWithKDistinct(int[] A, int K) {
if (Objects.isNull(A) || A.length == 0 || A.length < K) {
return 0;
}
int[] hash = new int[A.length + 1];
int left = 0, count = 0;
int results = 0, result = 1;
for (int right = 0; right < A.length; right++) {
hash[A[right]]++;
if (hash[A[right]] == 1) {
count++;
}
while (hash[A[left]] > 1 || count > K) {
if (count > K) {
result = 1;
count--;
} else {
result++;
}
hash[A[left]]--;
left++;
}
if (count == K) {
results += result;
}
}
return results;
}
/**
* Runtime: 53 ms, faster than 67.75% of Java online submissions for Subarrays with K Different Integers.
* Memory Usage: 43.9 MB, less than 10.53% of Java online submissions for Subarrays with K Different Integers.
*
* Copy from: https://leetcode-cn.com/problems/subarrays-with-k-different-integers/solution/k-ge-bu-tong-zheng-shu-de-zi-shu-zu-by-leetcode/[K 个不同整数的子数组 - K 个不同整数的子数组 - 力扣（LeetCode）]
*/
public int subarraysWithKDistinctWindows(int[] A, int K) {
if (Objects.isNull(A) || A.length == 0 || A.length < K) {
return 0;
}
Window w1 = new Window();
Window w2 = new Window();
int result = 0;
int left1 = 0, left2 = 0;
for (int right = 0; right < A.length; right++) {
int x = A[right];
w1.add(x);
w2.add(x);
while (w1.different() > K) {
w1.remove(A[left1++]);
}
while (w2.different() >= K) {
w2.remove(A[left2++]);
}
result += left2 - left1;
}
return result;
}
private class Window {
Map<Integer, Integer> count;
int nonzeo;
public Window() {
count = new HashMap<>();
nonzeo = 0;
}
void add(int x) {
count.put(x, count.getOrDefault(x, 0) + 1);
if (count.get(x) == 1) {
nonzeo++;
}
}
void remove(int x) {
count.put(x, count.get(x) - 1);
if (count.get(x) == 0) {
nonzeo--;
}
}
int different() {
return nonzeo;
}
}