Re: [閒聊] 每日leetcode
題目
請問有多少個子字串裡面有至少k對相同的數字
思路1
我的好像有點怪 不過很酷
先算出總共有幾個子字串
用sliding window 找到小於k對的子字串
然後慢慢減掉就好了
姆咪
思路2 (一般的)
只要sliding window + hash map記錄就好
確保windows 裡面有剛好k組的話
要+的數量就是每次的l
反正裡面的k一定會比較多
姆咪
||```cpp
class Solution {
public:
long long countGood(vector<int>& nums, int k)
{
int n = nums.size();
long long res = (long long)n*(n+1)/2;
int l = 0 ;
int r = 0 ;
long long now = 0;
unordered_map<int,long long> save;
for(; r < n ; r ++)
{
int num = nums[r];
now += save[num];
save[num] ++;
while(now >= k && l <= r )
{
int lnum = nums[l];
now -= save[lnum]-1;
save[lnum] --;
l ++;
}
res -= r-l+1;
}
// res -= r-l+1;
return res;
}
};
```||
--
邊版的小母雞 — fuckchicken
https://i.imgur.com/wglAuYR.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.16.243 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1744792796.A.768.html
推
04/16 16:41,
7月前
, 1F
04/16 16:41, 1F
→
04/16 16:50,
7月前
, 2F
04/16 16:50, 2F
推
04/16 16:53,
7月前
, 3F
04/16 16:53, 3F
→
04/16 16:56,
7月前
, 4F
04/16 16:56, 4F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1397 之 1548 篇)：