2799. Count Complete Subarrays in an Array
You are given an array nums consisting of positive integers.
We call a subarray of an array complete if the following condition is satisfied:
- The number of distinct elements in the subarray is equal to the number of distinct elements in the whole array.
Return the number of complete subarrays.
A subarray is a contiguous non-empty part of an array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int countCompleteSubarrays(vector<int>& nums) {
unordered_map<int, int> freq;
for(auto& n : nums) freq[n] += 1;
int res = 0, target = freq.size();
unordered_map<int, int> now;
for(int l = 0, r = 0; l < nums.size() and freq.size() == target; l++) {
while(r < nums.size() and now.size() < target) now[nums[r++]] += 1;
res += nums.size() - r + 1;
if(--freq[nums[l]] == 0) freq.erase(nums[l]);
if(--now[nums[l]] == 0) now.erase(nums[l]);
}
return res;
}
};
|
