Re: [閒聊] 每日leetcode已回收
※ 引述 《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
→
03/30 22:13,
1年前
, 1F
03/30 22:13, 1F
→
03/30 22:15,
1年前
, 2F
03/30 22:15, 2F
推
03/30 22:24,
1年前
, 3F
03/30 22:24, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 80 之 1549 篇)：