k 个不同整数的子数组
解题思路：
-
题目是要找到 连续的子数组中不同元素个数等于 K 的数组个数，等于的情况很复杂，要考虑滑动窗口的范围缩减；
-
类比：要找到数组中等于 2 的个数 = 小于等于 2 的个数 - 小于等于 1 的个数；
-
即：「K 个不同整数的子区间的个数」= atMostWithKDistinct(A, K) - atMostWithKDistinct(A, K - 1)；
图解：
复杂度：
-
时间复杂度：O(N)，这里 N 是输入数组的长度；
-
空间复杂度：O(N)，使用了常数个变量、频数数组的长度为 N + 1；
代码实现：
function subarraysWithKDistinct(nums: number[], k: number): number {
return atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1);
}
// 左边界不动求小于等于 k 的子数组个数
function atMostKDistinct(nums: number[], k: number): number {
let len: number = nums.length;
let freq: Array<number> = new Array(len + 1).fill(0);
// [left, right) 里不同整数的个数
let left: number = 0, right: number = -1;
let count: number = 0, res: number = 0;
// [left, right) 包含不同整数的个数小于等于 K
while (++right < len) {
if (freq[nums[right]] == 0) {
count++;
}
freq[nums[right]]++;
// count>k，向右移动窗口左边界，直到 count<=K
while (count > k) {
freq[nums[left]]--;
if (freq[nums[left]] == 0) {
count--;
}
left++;
}
// right - left +1 为子数组的个数
res += right - left + 1;
}
return res;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
49.字母异位词分组
上一篇
评论
