992. Subarrays with K Different Integers

T: O(n)
S: O(n)

```java
class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        int subarrayWithAtMostK = subarrayWithAtMostK(nums, k);
        int subarrayWithAtMostKMinusOne = subarrayWithAtMostK(nums, k-1);

        return subarrayWithAtMostK - subarrayWithAtMostKMinusOne;
    }
    private int subarrayWithAtMostK(int[] nums, int k) {
        int n = nums.length;
        int left = 0;
        int result = 0;
        Map<Integer, Integer> freqMap = new HashMap<>();

        for (int right = 0; right < n; right++) {
            int rightNum = nums[right];
            freqMap.put(rightNum, freqMap.getOrDefault(rightNum, 0)+1);

            while (left <= right && freqMap.size() > k) {
                int leftNum = nums[left];
                freqMap.put(leftNum, freqMap.getOrDefault(leftNum, 0)-1);
                if (freqMap.get(leftNum) == 0) {
                    freqMap.remove(leftNum);
                }
                left++;
            }
            result += (right - left + 1);
        }
        return result;
    }
}

/**
T: O(n)
S: O(n)


 0 1 2 3 4
[1,2,1,2,3]
         r
       l


1 + 2 + 3 + 4 + 2

r - l + 1 -> length is (r - l + 1) 's subarray can be these: 

[1] -> 1
   [1,2][2] -> 2
   [2,1'], [1,2,1'] [1']. -> 3

   4:
    [1,2,1,2]
     [2,1,2']
     [1,2']
     [2']

   2: [2',3], [3]  

above inclue 1 distinct, so we have to subtract it


Consider nums = [1, 2, 1, 2, 3] and k = 2.
slidingWindowAtMost(nums, 2) will count all subarrays (12) with at most 2 distinct elements (including those with exactly 2 and 1).
slidingWindowAtMost(nums, 1) will count all subarrays (5) with at most 1 distinct element.

The difference, slidingWindowAtMost(nums, 2) - slidingWindowAtMost(nums, 1), 
removes subarrays with 1 distinct element, leaving only those with exactly 2, which is our answer (7).

 */
```