SHARE
TWEET

Untitled

a guest May 22nd, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int subarraysWithKDistinct(vector<int>& A, int K) {
  4.         return SubarraysWithAtMostKDistinct(A, K) - SubarraysWithAtMostKDistinct(A, K - 1);
  5.     }
  6. private:
  7.     int SubarraysWithAtMostKDistinct(const vector<int>& A, int K) {
  8.         if (K <= 0) return 0;
  9.         int distinct_subarrs = 0;
  10.         int curr_distinct = 0;
  11.         int lo = 0;
  12.         int hi = 0;
  13.        
  14.         vector<int> count(A.size() + 1);
  15.        
  16.         while (hi < A.size()) {
  17.             while (hi < A.size() && curr_distinct <= K) {
  18.                 if (count[A[hi]] == 0) ++curr_distinct;
  19.                 ++count[A[hi]];
  20.                 ++hi;
  21.                 if (curr_distinct <= K) distinct_subarrs += (hi - lo);
  22.             }
  23.            
  24.             if (curr_distinct <= K) break;
  25.            
  26.             while (curr_distinct > K) {
  27.                 --count[A[lo]];
  28.                 if (count[A[lo]] == 0) --curr_distinct;
  29.                 ++lo;
  30.             }
  31.            
  32.             distinct_subarrs += (hi - lo);
  33.         }
  34.        
  35.         return distinct_subarrs;
  36.     }
  37. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top