2799: Count-Complete-Subarrays-in-an-Array
Medium
table of contents
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;
}
};