992. Subarrays with K Different Integers

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1);
    }

    private int atMostKDistinct(int[] nums, int k) {
        int i = 0, j = 0; // [i, j]
        int[] count = new int[nums.length + 1];
        int distinct = 0, res = 0;

        while (j < nums.length) {
            if (count[nums[j]]++ == 0) {
                // 当前字符是一个新的不重复字符
                distinct++;
            }

            while (distinct > k) {
                // 此时不重复字符数已经大于 k, 缩小窗口
                if (--count[nums[i++]] == 0) {
                    distinct--;
                }
            }

            res += j - i + 1;
            j++;
        }

        return res;
    }
}

References

992. Subarrays with K Different Integers