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 <= 200001 <= A[i] <= A.length1 <= K <= A.length
Solution: Two pointers + indirection
Let f(x) denote the number of subarrays with x or less distinct numbers.
ans = f(K) – f(K-1)
It takes O(n) Time and O(n) Space to compute f(x)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // vector: 56 ms, 10.1 MB // Hashtable: 126 ms, 25 MB class Solution { public: int subarraysWithKDistinct(vector<int>& A, int K) { // Returns the number of subarrays with k or less distinct numbers. auto subarrys = [&A](int k) { vector<int> count(A.size() + 1); int ans = 0; int i = 0; for (int j = 0; j < A.size(); ++j) { if (count[A[j]]++ == 0) --k; while (k < 0) if (--count[A[i++]] == 0) ++k; ans += j - i + 1; } return ans; }; return subarrys(K) - subarrys(K - 1); } }; |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment