3,4], k = 3 Output: 3 Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Constraints

1 <= nums.length <= 2 * 10^4
1 <= nums[i], k <= nums.length

Solution

Method 1 - Sliding Window (at most K) Trick

Intuition

The number of subarrays with exactly K different integers is equal to the number with at most K minus the number with at most K-1. We can use a sliding window to count subarrays with at most K different integers efficiently.

Approach

Implement a helper function that returns the number of subarrays with at most K different integers using a sliding window and a hash map.
The answer

Related Tags