992. Subarrays with K Different Integers ----H ~~~~

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

 

Note:

1. 1 <= A.length <= 20000
2. 1 <= A[i] <= A.length
3. 1 <= K <= A.length

A:

就是sliding windows.  但是不同是， 以前我们只要求最长的。现在要求找到每一个。

因此这里，我们找到等于K的时候， 要虚拟从左边往右边缩小

而如果超过K，我们先去掉刚刚加入的，然后从左边开始缩小，直到map.size() 小于K

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        unordered_map<int, int> M;        
        int start = -1;
        int res = 0;
        for(int end = 0;end <A.size();end++){
            M[A[end]]++;
            if(M.size()<K)
                continue;
            if(M.size() == K){
                int runner = start;
                vector<int> tmpV;
                while(M.size() == K){// virtually shrink by one
                    res++;
                    int delVal = A[++runner];  
                    M[delVal]--;
                    if(M[delVal]==0){
                        M.erase(delVal);
                    }
                    tmpV.push_back(delVal);
                }
                for(auto k : tmpV){ // add back 
                    M[k]++;
                }
            }else{ // M.size() > K
                // newly added char is first added in the sliding window
                M.erase(A[end]); // remove first
                while( M.size() >= K){
                    int delVal = A[++start];
                    M[delVal]--;
                    if(M[delVal] ==0){
                        M.erase(delVal);
                    }
                }
                end--;  // redo this position again.
            }
        }
        return res;
    }
};