楼主:
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]