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 <= A.length <= 20000
1 <= A[i] <= A.length
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; } };
No comments:
Post a Comment