992. Subarrays with K Different Integers

yPhantom 2019年10月24日 36次浏览

原题链接

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

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].

Solution

题意求一个数组中的连续几个数字恰好有k个不同。窗口法。

但是需要转化一下。Exactly(k)=AtMost(k) - AtMost(k - 1)

Java版

class Solution {
    public int subarraysWithKDistinct(int[] A, int K) {
        return atMost(A, K) - atMost(A, K - 1);
    }
    
    private int atMost(int[] A, int K) {
        HashMap<Integer, Integer> count = new HashMap<>();
        int left = 0;
        int n = A.length;
        int res = 0;
        for(int right = 0; right < n; right++) {
            if (count.getOrDefault(A[right], 0) == 0) {
                K--;
            }
            count.put(A[right], count.getOrDefault(A[right], 0) + 1);
            while (K < 0) {
                count.put(A[left], count.get(A[left]) - 1);
                if (count.get(A[left]) == 0) {
                    K++;
                }
                left++;
            }
            res += right - left + 1;
        }
        return res;
    }
}