【LeetCode刷题-滑动窗口】--992.K个不同整数的子数组

992.K个不同整数的子数组

思路：

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return atMostKDistinct(nums,k) - atMostKDistinct(nums,k-1);
    }
    //最多包含K个不同整数的子区间个数
    private int atMostKDistinct(int[] a,int k){
        int len = a.length;
        int[] freq = new int[len + 1];
        
        int left = 0,right = 0;
        int count = 0,res = 0;
        //[left,right)里不同整数的个数
        while(right < len){
            if(freq[a[right]] == 0){
                count++;
            }
            freq[a[right]]++;
            right++;
            while(count > k){
                freq[a[left]]--;
                if(freq[a[left]] == 0){
                    count--;
                }
                left++;
            }
            res += right - left;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30