2537: Count-the-Number-of-Good-Subarrays
Medium
A classic two pointers / sliding window question.
Simply iterate the r index of the sliding window
until there are at least k pairs, 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 then consequently add
mp[nums[i]]-1 pairs (since logically speaking, the
addition of the new value into the sliding window
adds mp[nums[i]]-1 pairs).
Then, if there are more than k pairs, we can add
nums.size() - r + 1 to the number of
feasible subarrays. Finally, before we increment
our l index, we decrement mp[nums[l]]
and then remove mp[nums[i]] pairs, before repeating
this all over again until either the r index
exceeds the length of the array or the number of
pairs is smaller than k.
Code:
class Solution {
public:
long long countGood(vector<int>& nums, int k) {
unordered_map<int, int> mp;
int l = 0, r = 0, counter = 0;
long long ans = 0;
for (; r < nums.size() || counter >= k;) {
for (; r < nums.size() && counter < k; ++r) {
++mp[nums[r]];
counter += (mp[nums[r]]-1);
}
if (counter >= k) {
ans += nums.size()-r+1;
}
--mp[nums[l]];
counter -= mp[nums[l]];
++l;
}
return ans;
}
};