Subarrays with K Different Integers

Given an arrayAof positive integers, call a (contiguous, not necessarily distinct) subarray ofA_good_if the number of different integers in that subarray is exactlyK.

(For example,[1,2,3,1,2]has3different integers:1,2, and3.)

Return the number of good subarrays ofA.

Example

Example 1:

Input: 
A = [1,2,1,2,3], K = 2

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

Example 2:

Input: 
A = [1,2,1,3,4], K = 3

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

Note

关键是求刚好K个不同的，参考之前的最多k个不同

numAtMostK(nums, k) - numAtMostK(nums, k - 1);

子串最多有k个不同的，满足条件的最大长度的窗口长度为就为个数

Code

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

    private int numAtMostK(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int j = 0;
        int len = nums.length;
        int count = 0;
        int res = 0;
        for (int i = 0; i < len; i++) {
            while (j < len && count <= k) {
                map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);
                if (map.get(nums[j]) == 1) {
                    if (count == k) {
                        map.put(nums[j], map.get(nums[j]) - 1);
                        break;
                    }
                    count++;
                }
                j++;
            }
            res += j - i;
            if (map.getOrDefault(nums[i], 0) == 1) {
                count--;
            }
            map.put(nums[i], map.get(nums[i]) - 1);   
        }

        return res;
    }
}