作者:
oin1104 (是oin的說)
2025-04-16 16:39:54題目
請問有多少個子字串裡面有至少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]