※ 引述 《JIWP (神楽めあ的錢包)》 之銘言：
:
: 這題acceptance rate有57%應該算是hard裡面比較簡單的
:
: 992. Subarrays with K Different Integers
:
: 有一個array nums、整數 k
:
: 定義good subarrays:
:
: 當一個subarray裡有k種不同的整數，那這個sub array就是good subarray
:
我的想法也差不多
不過一開始我是用vextor把每個數字出現過的index都紀錄下來
後來TLE
然後才發現只要記錄可以縮的window 的最右邊就可以了
要刪除那種數字的時候就慢慢移過去
剛好對到的話代表他是最後一個
直接刪除就好
姆咪
然後這是畫圖跟咩阿
https://i.imgur.com/PasXQAM.jpg
class Solution {
public:
int subarraysWithKDistinct(vector<int>& nums, int k) {
int len = nums.size();
int res = 0;
unordered_map<int,int> paper;
int l = 0;
int r = 0;
for(; r < len ; r ++)
{
paper[nums[r]] = r;
while(paper.size() > k)
{
if(paper[nums[l]] == l)
{
paper.erase(nums[l]);
}
l++;
}
if(paper.size() == k)
{
int plus = 200000;
for(auto pp : paper)
{
plus = min(pp.second,plus);
}
res += plus - l + 1;
}
}
return res;
}
};