力扣992.K个不同整数的子数组
-
atmostK()函数求最多K个不同字符的子串数量
- 则本题 恰好K个 可以转化成 最多K个 – 最多K–1个
-
class Solution {public:int atMostK(vector<int> nums,int k){int n = nums.size();unordered_map<int,int> cnt;int res=0;for(int i=0,j=0;i<n;i++){cnt[nums[i]] ++;while(cnt.size() > k){if(-- cnt[nums[j]] == 0) cnt.erase(nums[j]);j ++;}res += i - j + 1;}return res;}int subarraysWithKDistinct(vector<int>& nums, int k) {return atMostK(nums,k) - atMostK(nums,k-1);}};
