Subarrays with K Different Integers
HardArrayHash TableSliding WindowCounting
Solution
export function subarraysWithKDistinct(nums: number[], k: number): number {
const n = nums.length;
const counts = new Array(n + 1).fill(0);
let answer = 0;
let [start, mid] = [0, 0];
let remain = k;
for (const num of nums) {
counts[num] += 1;
if (counts[num] === 1) {
remain -= 1;
if (remain < 0) {
counts[nums[mid]] = 0;
mid += 1;
start = mid;
}
}
if (remain <= 0) {
while (1 < counts[nums[mid]]) {
counts[nums[mid]] -= 1;
mid += 1;
}
answer += mid - start + 1;
}
}
return answer;
}