subarraysWithKDistinct
unknown
c_cpp
a year ago
791 B
4
Indexable
class Solution { public: int subarraysWithAtmostK(vector<int>& nums, int k) { map<int,int> numFrequency; int count = 0; int i = 0 , j = 0, n = nums.size(); while( j < n ) { numFrequency[nums[j]]++; while( i <= j && numFrequency.size() > k ) { numFrequency[nums[i]]--; if( numFrequency[nums[i]] == 0 ) numFrequency.erase(nums[i]); i++; } count += j-i+1; j++; } return count; } int subarraysWithKDistinct(vector<int>& nums, int k) { return subarraysWithAtmostK(nums,k) - subarraysWithAtmostK(nums,k-1) ; } };
Editor is loading...
Leave a Comment