2026-06-29：统计包含 K 个不同整数的子数组。用go语言，给定一个整数数组 nums，以及两个整数 k 和 m。你需要统计数组中连续的非空子数组有多少个。

对任意一个子数组，如果它满足：

这个子数组里一共有恰好 k 个不同的数；

1.对于这 k 个不同的数中的每一个，它在该子数组中出现的次数都不少于 m；

2.那么这个子数组就算作满足条件的一个。

最终返回满足上述要求的子数组总数。

1 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

1 <= k, m <= nums.length。

输入： nums = [1,2,1,2,2], k = 2, m = 2。

输出： 2。

解释：

满足条件的子数组为：

因此，答案是 2。

题目来自力扣3859。

一、解题核心思路整体概述

题目要求统计恰好拥有k种不同数字，且这k种数字每一种在子数组内出现次数都≥m的连续子数组数量。
直接求「恰好k个」很难滑动窗口一次性算出，因此采用经典容斥差分思想：
满足恰好k种的合法子数组总数 = calc(k) − calc(k+1)
其中函数calc(t)的定义：统计不同数字种类 ≤ t，且窗口内≥m次的数字总数≥k的所有子数组数量。

• calc(k)：所有不同数≤k、且有至少k种数字出现≥m次的子数组；
• calc(k+1)：所有不同数≤k+1、且有至少k种数字出现≥m次的子数组；
  两者相减后，剩下的就是不同数字严格等于k种、且这k种全部出现≥m次的目标子数组。

二、calc(t) 函数完整分步执行逻辑（滑动窗口双指针，左边界left，右边界逐个右移）

calc(t) 内部使用不定长滑动窗口（双指针left、right），right循环逐个取数组元素作为窗口右边界，left只向右移动不回退，全程维护3个核心变量：

1. cnt哈希map：记录当前窗口 [left, right] 内每个数字的出现次数；
2. geM：当前窗口内出现次数 ≥ m的数字总个数；
3. left：窗口左边界下标，所有以当前right为右端点、满足约束的合法子数组左起点都在 [0, left-1]，因此每次累加left到答案。

逐轮标准三步流程（每处理一个右边界元素x = nums[right]）

步骤1：将当前右边界元素x加入窗口，更新计数与geM

1. 哈希表 cnt[x] 计数+1；
2. 特殊判断：如果自增后 cnt[x] 刚好等于 m，说明这个数字第一次达到≥m次，geM 计数 +1；
   • 若原本cnt[x]已经大于m，自增后依旧≥m，geM不变化。

步骤2：收缩左边界left，直到窗口不满足两个约束条件之一

约束条件（需要持续收缩窗口的触发条件）：
窗口不同数字总数 len(cnt) ≥ t 并且 geM ≥ k
只要同时满足上面两条，就不断把最左侧元素nums[left]移出窗口：

1. 取出待移除元素 out = nums[left]；
2. 若 cnt[out] 恰好等于 m：移除后该数字出现次数会小于m，因此geM 计数 -1；
3. cnt[out] 计数-1；
4. 若减完后 cnt[out] == 0：该数字在窗口内完全消失，从哈希表cnt中删除，窗口不同数字种类数len(cnt)自动减少；
5. left指针向右移动一位，重复判断约束条件，直到不再同时满足「len(cnt)≥t、geM≥k」才停止收缩。

收缩完成后，窗口 [left, right] 是以right为右端点、满足 len(cnt)<t 或 geM<k 的最小左边界窗口。
所有起点在 0 ~ left-1 的子数组 [s, right]（s < left），全部满足len(cnt) ≤ t 且 geM ≥ k，都是calc(t)要统计的合法子数组。

步骤3：累加当前合法子数组数量到ans

以当前right为右端点的合法子数组一共有 left 个（起点0、1……left-1，共left个），执行ans += int64(left)。

calc(t) 函数返回值

遍历完数组所有右边界后，ans即为全部「不同数字≤t、且至少k种数字出现≥m次」的子数组总数。

三、完整样例推演：nums=[1,2,1,2,2], k=2, m=2

最终答案 = calc(2) − calc(3)

1. 先计算 calc(2)：统计不同数≤2、geM≥2 的子数组总数

数组下标0~4：[1,2,1,2,2]，t=2，k=2，m=2
初始化 cnt空map、geM=0、left=0、ans=0

right=0，x=1

1. 入窗口：cnt[1]=1，不等于2 → geM不变0
2. 收缩判断：len(cnt)=1 <2，不收缩，left保持0
3. ans += 0 → ans=0

right=1，x=2

1. 入窗口：cnt[2]=1，geM=0
2. len(cnt)=2≥2，但geM=0<2，不收缩，left=0
3. ans +=0 → ans=0

right=2，x=1

1. cnt[1]变为2，恰好等于m=2 → geM=1
2. len(cnt)=2≥2，geM=1<2，不收缩，left=0
3. ans +=0 → ans=0

right=3，x=2

1. cnt[2]变为2，等于m=2 → geM=2
2. 触发收缩条件：len(cnt)=2≥2 && geM=2≥2，开始移出左元素out=1（left=0）
   • cnt[out]=2 == m → geM=1
   • cnt[1]减为1，不为0，不删除map键
   • left变为1
     再次判断：len(cnt)=2≥2，但geM=1<2，停止收缩
3. ans += left=1 → ans=1
   含义：以下标3为右端点，起点0的子数组[0,3]满足calc(2)条件，计1个

right=4，x=2

1. cnt[2]变为3，大于m=2，geM不变仍为1
2. len(cnt)=2≥2，geM=1<2，不收缩，left保持1
3. ans += left=1 → ans=2
   calc(2)最终返回 ans=2

2. 再计算 calc(3)：统计不同数≤3、geM≥2 的子数组总数

数组只有1、2两种数字，len(cnt)永远≤2 ❤️，全程不会触发窗口收缩逻辑，left始终固定为0
每一轮 ans += 0，遍历完成后 calc(3)=0

3. 差分计算最终结果

calc(2) − calc(3) = 2 − 0 = 2，与题目输出一致。

四、算法时间复杂度分析

1. calc函数执行两次：calc(k)、calc(k+1)，两次逻辑完全相同；
2. 单次calc内滑动窗口特性：right指针完整遍历数组一次（O(n)），left指针只会单向右移，最多移动n次，无回退；哈希表增删改查单次操作均为均摊O(1)；
3. 单次calc时间复杂度 O(n)，两次调用总时间复杂度O(n)，n为nums数组长度；
   可满足题目 n ≤ 1e5 的数据规模。

五、算法额外空间复杂度分析

仅哈希表cnt占用额外空间，哈希表存储窗口内不重复数字；
最坏情况数组所有数字互不相同，哈希表存储全部n个数字；
额外空间复杂度O(n)。

Go完整代码如下：

packagemainimport("fmt")funccountSubarrays(nums[]int,k,mint)int64{calc:=func(distinctLimitint)(ansint64){cnt:=map[int]int{}geM:=0// 窗口中的出现次数 >= m 的元素个数left:=0for_,x:=rangenums{// 1. 入cnt[x]++ifcnt[x]==m{geM++}// 2. 出forlen(cnt)>=distinctLimit&&geM>=k{out:=nums[left]ifcnt[out]==m{geM--}cnt[out]--ifcnt[out]==0{delete(cnt,out)}left++}// 3. 更新答案ans+=int64(left)}return}returncalc(k)-calc(k+1)}funcmain(){nums:=[]int{1,2,1,2,2}k:=2m:=2result:=countSubarrays(nums,k,m)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-fromtypingimportListdefcountSubarrays(nums:List[int],k:int,m:int)->int:# 内部函数：统计满足 不同元素个数 >= distinctLimit 且# 出现次数 >= m 的元素个数 >= k 的子数组个数defcalc(distinctLimit:int)->int:cnt={}# 当前窗口中各元素的出现次数geM=0# 出现次数 >= m 的元素个数left=0ans=0forxinnums:# 1. 将右端点元素加入窗口cnt[x]=cnt.get(x,0)+1ifcnt[x]==m:geM+=1# 2. 当窗口满足条件时，收缩左边界直到条件不再满足whilelen(cnt)>=distinctLimitandgeM>=k:out=nums[left]ifcnt[out]==m:geM-=1cnt[out]-=1ifcnt[out]==0:delcnt[out]left+=1# 3. 对于当前右端点，所有左端点 < left 的子数组均满足条件ans+=leftreturnans# 容斥：不同元素个数恰好为 k，且每个元素的出现次数都 >= mreturncalc(k)-calc(k+1)if__name__=="__main__":nums=[1,2,1,2,2]k=2m=2result=countSubarrays(nums,k,m)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<unordered_map>usingnamespacestd;longlongcountSubarrays(constvector<int>&nums,intk,intm){// 内部函数：统计满足 不同元素个数 >= distinctLimit 且// 出现次数 >= m 的元素个数 >= k 的子数组个数autocalc=[&](intdistinctLimit)->longlong{unordered_map<int,int>cnt;intgeM=0;// 出现次数 >= m 的元素个数intleft=0;longlongans=0;for(intx:nums){// 1. 将右端点元素加入窗口cnt[x]++;if(cnt[x]==m){geM++;}// 2. 当窗口满足条件时，收缩左边界直到条件不再满足while((int)cnt.size()>=distinctLimit&&geM>=k){intout=nums[left];if(cnt[out]==m){geM--;}cnt[out]--;if(cnt[out]==0){cnt.erase(out);}left++;}// 3. 对于当前右端点，所有左端点 < left 的子数组均满足条件ans+=left;}returnans;};// 容斥：不同元素个数恰好为 k，且每个元素的出现次数都 >= mreturncalc(k)-calc(k+1);}intmain(){vector<int>nums={1,2,1,2,2};intk=2,m=2;longlongresult=countSubarrays(nums,k,m);cout<<result<<endl;return0;}