题目链接
给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。
（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3）
返回 A 中好子数组的数目。
示例 1：
1
2
3
| 输入：A = [1,2,1,2,3], K = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
|
示例 2：
1
2
3
| 输入：A = [1,2,1,3,4], K = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
|
思维+双指针~
利用双指针，当我们固定左端点时，可以找到恰好存在 K 个不同整数的最大右边界 $R$，那么我们只需找到最小左边界 $L$，答案就是 $R-L+1$，那么这个最小左边界怎么找呢，我们可以再加一个指针，这个指针指向恰好存在 K-1 个不同整数的最大右边界 $R’$，答案就是 $R-R’$，AC代码如下：
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
| class Solution {
public:
int subarraysWithKDistinct(vector<int> &A, int K) {
int n = A.size();
vector<int> num1(n + 1), num2(n + 1);
int sum1 = 0, sum2 = 0;
int l1 = 0, l2 = 0, r = 0, ans = 0;
while (r < n) {
if (!num1[A[r]]) sum1++;
num1[A[r]]++;
if (!num2[A[r]]) sum2++;
num2[A[r]]++;
while (sum1 > K) {
num1[A[l1]]--;
if (!num1[A[l1]]) sum1--;
l1++;
}
while (sum2 > K - 1) {
num2[A[l2]]--;
if (!num2[A[l2]]) sum2--;
l2++;
}
ans += l2 - l1;
r++;
}
return ans;
}
};
|