2020-04-25 18:39:55
问题描述：
给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。
（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
返回 A 中好子数组的数目。
示例 1：
输入：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：
输入：A = [1,2,1,3,4], K = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
提示：
1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length
问题求解：
直接去求解子区间有恰好k个不同的元素比较困难，如果替换为求解at most k的话就会容易很多。
时间复杂度：O(n)
public int subarraysWithKDistinct(int[] A, int K) {
return helper(A, K) - helper(A, K - 1);
}
private int helper(int[] nums, int k) {
int n = nums.length;
int res = 0;
int start = 0;
int cnt = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int end = 0; end < n; end++) {
map.put(nums[end], map.getOrDefault(nums[end], 0) + 1);
if (map.get(nums[end]) == 1) cnt += 1;
while (cnt > k) {
map.put(nums[start], map.get(nums[start]) - 1);
if (map.get(nums[start]) == 0) cnt -= 1;
start += 1;
}
res += end - start + 1;
}
return res;
}
原文：https://www.cnblogs.com/hyserendipity/p/12774449.html