Subarrays with K Different Integers

The interview that broke my streak. I had every sliding-window template memorized but this one asks for exactly K distinct, not at most K, and my reflexive at-most window came up short. The trick (subtract two at-most windows: atMost(K) - atMost(K - 1)) reframes a hard counting question as two easy ones. It is the prettiest sliding-window pattern I know, and FAANG asks it regularly under different costumes (subarrays with K odd numbers, substrings with K vowels, etc.).

Subarrays with K Different Integers

Given an integer array nums and an integer k, return the number of good subarrays of nums. A good subarray is a contiguous subarray that contains exactly k different integers.

Examples

Example 1:

• Input: nums = [1, 2, 1, 2, 3], k = 2
• Output: 7
• Explanation: Good subarrays: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]. Seven in total.

Example 2:

• Input: nums = [1, 2, 1, 3, 4], k = 3
• Output: 3
• Explanation: Good subarrays: [1, 2, 1, 3], [2, 1, 3], [1, 3, 4].

Example 3:

• Input: nums = [1, 1, 1, 1], k = 1
• Output: 10
• Explanation: Every contiguous subarray contains the single distinct value 1. With n = 4, the count is 4 + 3 + 2 + 1 = 10.

Example 4:

• Input: nums = [1, 2], k = 3
• Output: 0
• Explanation: Cannot have 3 distinct integers in an array of 2 elements.

Constraints

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

Follow-up

Can you solve it in a single pass that maintains two left pointers (one tight, one loose) instead of running two at-most passes? It is doable but trickier; the two-pass version is cleaner to reason about and the constants are nearly identical.