2537. Count the Number of Good Subarrays
Given an integer array nums and an integer k, return the number of good subarrays of nums.
A subarray arr is good if it there are at least k pairs of indices (i, j) such that i < j and arr[i] == arr[j].
A subarray is a contiguous non-empty sequence of elements within an array.
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
long long countGood(vector<int>& A, int k) {
long long res = 0, l = 0, r = 0, n = A.size(), now = 0;
unordered_map<long long, long long> freq;
for(; r < n; r++) {
now += freq[A[r]];
freq[A[r]] += 1;
if(now >= k) {
while(l < r) {
long long cut = freq[A[l]] - 1;
if(now - cut >= k) {
now -= cut;
freq[A[l]] -= 1;
l += 1;
} else break;
}
res += l + 1;
}
}
return res;
}
};
|
