Leetcode: 992. Subarrays with K Different Integers

URL : https://leetcode.com/problems/subarrays-with-k-different-integers/
思路：
该题其实代码量不多，但是思路不好想，我是看了discuss才恍然大悟。下面给出代码。
数组中最多出现K个不同的数字的组合数为N， 数组中最多出现K-1个不同的数字的组合数为M，则我们想要的结果是出现K个不同的组合数N-M.
最多出现K个不同的数字的组合数的计算方法则相对简单啦，使用滑动窗口，在窗口内的不同数字不超过K就行了。

public int subarraysWithKDistinct(int[] A, int K) {
        return AtMost(A,K) - AtMost(A, K-1);
    }


    public int AtMost(int[]A, int k) {

        int[] map = new int[20001];
        int pre=0;int res=0;
        int count = 0;
        for (int i=0;i<A.length;i++) {
            map[A[i]]++;
            if (map[A[i]] == 1) {
                count++;
            }
            if (count <= k){
                res += i- pre +1;
            }
            while(count > k) {
                int tmp = map[A[pre]];
                if (tmp == 1) {
                    res += i - pre;
                    count--;
                }
                map[A[pre++]]--;
            }
        }
        return res;
    }

最后

以上就是平常火车为你收集整理的Leetcode: 992. Subarrays with K Different Integers的全部内容，希望文章能够帮你解决Leetcode: 992. Subarrays with K Different Integers所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。