一、題目

二、思路

2.1 解題思路

2.2 代碼嘗試

class Solution {
public:int subarraysWithKDistinct(vector<int>& nums, int k) {//需要有數據結構來存儲數組統計情況，還是采用哈希表unordered_map<int,int> map;int ret=0;int l=0,r=0;while(r<nums.size()){//窗口先伸展到最大map[nums[r]]++;ret+=cnt?=r-l+1<k0:while(map.size()>k){if(map[nums[l]]!=0){map[nums[l]]--;}else{map.erase[nums[l]];}l++;}}return ret;}
};

2.3 疑難問題

三、解法

class Solution {
public:int subarraysWithKDistinct(vector<int>& nums, int k) {int n = nums.size();vector<int> num1(n + 1), num2(n + 1);int tot1 = 0, tot2 = 0;int left1 = 0, left2 = 0, right = 0;int ret = 0;while (right < n) {if (!num1[nums[right]]) {tot1++;}num1[nums[right]]++;if (!num2[nums[right]]) {tot2++;}num2[nums[right]]++;while (tot1 > k) {num1[nums[left1]]--;if (!num1[nums[left1]]) {tot1--;}left1++;}while (tot2 > k - 1) {num2[nums[left2]]--;if (!num2[nums[left2]]) {tot2--;}left2++;}ret += left2 - left1;right++;}return ret;}
};作者：力扣官方題解
鏈接：https://leetcode.cn/problems/subarrays-with-k-different-integers/solutions/598045/k-ge-bu-tong-zheng-shu-de-zi-shu-zu-by-l-9ylo/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

四、收獲

4.1 心得

4.2 舉一反三

count(k)-count(k-1)的思想