2799: Count-Complete-Subarrays-in-an-Array
Medium
Another classic two-pointers / sliding-window question.
First, you have to iterate through the array nums
to find the number of unique values,
unique_count, present.
Simply iterate the r index of the sliding window
until there areunique_count numbers present, keeping
track of the number of occurences of a number in the sliding
window using the hash-map mp. When iterating through
the array nums, we can simply increment
mp[nums[r]] and check if this is the first instance
of the number inside the sliding window.
Then, if there are unique_count unique numbers
present, we can add nums.size() - r + 1 to the count
of subarrays with the maximum number of unique
numbers present. Finally, before we increment our l
index, we decrement mp[nums[l]] and then decrement
our count of unique numbers present in the sliding window if that
was the last occurence, before repeating this all over again until
either the r index exceeds the length of the
array or the number of unique numbers is smaller
than unique_count.
Code:
class Solution {
public:
int countCompleteSubarrays(vector<int>& nums) {
int mp[2001] = {0};
int unique_count = 0;
for (int num : nums) {
if (mp[num] == 0) {
++unique_count;
++mp[num];
}
}
memset(mp, 0, sizeof(mp));
int l = 0, r = 0, counter = 0, ans = 0;
for (;r < nums.size() || counter == unique_count;) {
for (; r < nums.size() && counter < unique_count; ++r) {
if (mp[nums[r]] == 0) {
++counter;
}
++mp[nums[r]];
}
if (counter == unique_count) {
ans += nums.size()-r+1;
}
--mp[nums[l]];
if (mp[nums[l]] == 0) {
--counter;
}
++l;
}
return ans;
}
};