Re: [閒聊] 每日leetcode

[oinishere (是oin捏)]

※ 引述 《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;
    }
};





--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.57.64 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1711808006.A.7C1.html
→ JIWP: 錢
→ oinishere: 你沒有
推 SecondRun: 錢錢