Solution: Subarrays with K Different Integers

Statement

You are given an integer array nums and an integer k. Your task is to return the number of good subarrays of nums.

A good subarray is a contiguous subarray that contains exactly k distinct integers. For example, in the array $[1, 2, 3, 1, 2]$, the subarray $[1, 2, 3]$contains $3$ distinct integers: $1$, $2$, and $3$.

Constraints:

• $1 \leq$ nums.length $\leq 2 * 10^{4}$

• $1 \leq$ nums[i], k $\leq$ nums.length

Solution

To count the number of subarrays that contain exactly k distinct integers, we use the sliding window pattern. Instead of directly identifying these subarrays, which would be computationally expensive, we calculate the result as the difference between the number of subarrays with at most k distinct integers and the number of subarrays with at most k - 1 distinct integers.