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

2026-06-29统计包含 K 个不同整数的子数组。用go语言给定一个整数数组 nums以及两个整数 k 和 m。你需要统计数组中连续的非空子数组有多少个。对任意一个子数组如果它满足这个子数组里一共有恰好 k 个不同的数1.对于这 k 个不同的数中的每一个它在该子数组中出现的次数都不少于 m2.那么这个子数组就算作满足条件的一个。最终返回满足上述要求的子数组总数。1 nums.length 100000。1 nums[i] 100000。1 k, m nums.length。输入 nums [1,2,1,2,2], k 2, m 2。输出 2。解释满足条件的子数组为子数组不同整数频率[1, 2, 1, 2]{1, 2} → 2{1: 2, 2: 2}[1, 2, 1, 2, 2]{1, 2} → 2{1: 2, 2: 3}因此答案是 2。题目来自力扣3859。一、解题核心思路整体概述题目要求统计恰好拥有k种不同数字且这k种数字每一种在子数组内出现次数都≥m的连续子数组数量。直接求「恰好k个」很难滑动窗口一次性算出因此采用经典容斥差分思想满足恰好k种的合法子数组总数 calc(k) − calc(k1)其中函数calc(t)的定义统计不同数字种类 ≤ t且窗口内≥m次的数字总数≥k的所有子数组数量。calc(k)所有不同数≤k、且有至少k种数字出现≥m次的子数组calc(k1)所有不同数≤k1、且有至少k种数字出现≥m次的子数组两者相减后剩下的就是不同数字严格等于k种、且这k种全部出现≥m次的目标子数组。二、calc(t) 函数完整分步执行逻辑滑动窗口双指针左边界left右边界逐个右移calc(t) 内部使用不定长滑动窗口双指针left、rightright循环逐个取数组元素作为窗口右边界left只向右移动不回退全程维护3个核心变量cnt哈希map记录当前窗口 [left, right] 内每个数字的出现次数geM当前窗口内出现次数 ≥ m的数字总个数left窗口左边界下标所有以当前right为右端点、满足约束的合法子数组左起点都在 [0, left-1]因此每次累加left到答案。逐轮标准三步流程每处理一个右边界元素x nums[right]步骤1将当前右边界元素x加入窗口更新计数与geM哈希表 cnt[x] 计数1特殊判断如果自增后 cnt[x] 刚好等于 m说明这个数字第一次达到≥m次geM 计数 1若原本cnt[x]已经大于m自增后依旧≥mgeM不变化。步骤2收缩左边界left直到窗口不满足两个约束条件之一约束条件需要持续收缩窗口的触发条件窗口不同数字总数 len(cnt) ≥ t 并且 geM ≥ k只要同时满足上面两条就不断把最左侧元素nums[left]移出窗口取出待移除元素 out nums[left]若 cnt[out] 恰好等于 m移除后该数字出现次数会小于m因此geM 计数 -1cnt[out] 计数-1若减完后 cnt[out] 0该数字在窗口内完全消失从哈希表cnt中删除窗口不同数字种类数len(cnt)自动减少left指针向右移动一位重复判断约束条件直到不再同时满足「len(cnt)≥t、geM≥k」才停止收缩。收缩完成后窗口 [left, right] 是以right为右端点、满足 len(cnt)t 或 geMk 的最小左边界窗口。所有起点在 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], k2, m2最终答案 calc(2) − calc(3)1. 先计算 calc(2)统计不同数≤2、geM≥2 的子数组总数数组下标0~4[1,2,1,2,2]t2k2m2初始化 cnt空map、geM0、left0、ans0right0x1入窗口cnt[1]1不等于2 → geM不变0收缩判断len(cnt)1 2不收缩left保持0ans 0 → ans0right1x2入窗口cnt[2]1geM0len(cnt)2≥2但geM02不收缩left0ans 0 → ans0right2x1cnt[1]变为2恰好等于m2 → geM1len(cnt)2≥2geM12不收缩left0ans 0 → ans0right3x2cnt[2]变为2等于m2 → geM2触发收缩条件len(cnt)2≥2 geM2≥2开始移出左元素out1left0cnt[out]2 m → geM1cnt[1]减为1不为0不删除map键left变为1再次判断len(cnt)2≥2但geM12停止收缩ans left1 → ans1含义以下标3为右端点起点0的子数组[0,3]满足calc(2)条件计1个right4x2cnt[2]变为3大于m2geM不变仍为1len(cnt)2≥2geM12不收缩left保持1ans left1 → ans2calc(2)最终返回 ans22. 再计算 calc(3)统计不同数≤3、geM≥2 的子数组总数数组只有1、2两种数字len(cnt)永远≤2 ❤️全程不会触发窗口收缩逻辑left始终固定为0每一轮 ans 0遍历完成后 calc(3)03. 差分计算最终结果calc(2) − calc(3) 2 − 0 2与题目输出一致。四、算法时间复杂度分析calc函数执行两次calc(k)、calc(k1)两次逻辑完全相同单次calc内滑动窗口特性right指针完整遍历数组一次O(n)left指针只会单向右移最多移动n次无回退哈希表增删改查单次操作均为均摊O(1)单次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)distinctLimitgeMk{out:nums[left]ifcnt[out]m{geM--}cnt[out]--ifcnt[out]0{delete(cnt,out)}left}// 3. 更新答案ansint64(left)}return}returncalc(k)-calc(k1)}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{}# 当前窗口中各元素的出现次数geM0# 出现次数 m 的元素个数left0ans0forxinnums:# 1. 将右端点元素加入窗口cnt[x]cnt.get(x,0)1ifcnt[x]m:geM1# 2. 当窗口满足条件时收缩左边界直到条件不再满足whilelen(cnt)distinctLimitandgeMk:outnums[left]ifcnt[out]m:geM-1cnt[out]-1ifcnt[out]0:delcnt[out]left1# 3. 对于当前右端点所有左端点 left 的子数组均满足条件ansleftreturnans# 容斥不同元素个数恰好为 k且每个元素的出现次数都 mreturncalc(k)-calc(k1)if__name____main__:nums[1,2,1,2,2]k2m2resultcountSubarrays(nums,k,m)print(result)C完整代码如下#includeiostream#includevector#includeunordered_mapusingnamespacestd;longlongcountSubarrays(constvectorintnums,intk,intm){// 内部函数统计满足 不同元素个数 distinctLimit 且// 出现次数 m 的元素个数 k 的子数组个数autocalc[](intdistinctLimit)-longlong{unordered_mapint,intcnt;intgeM0;// 出现次数 m 的元素个数intleft0;longlongans0;for(intx:nums){// 1. 将右端点元素加入窗口cnt[x];if(cnt[x]m){geM;}// 2. 当窗口满足条件时收缩左边界直到条件不再满足while((int)cnt.size()distinctLimitgeMk){intoutnums[left];if(cnt[out]m){geM--;}cnt[out]--;if(cnt[out]0){cnt.erase(out);}left;}// 3. 对于当前右端点所有左端点 left 的子数组均满足条件ansleft;}returnans;};// 容斥不同元素个数恰好为 k且每个元素的出现次数都 mreturncalc(k)-calc(k1);}intmain(){vectorintnums{1,2,1,2,2};intk2,m2;longlongresultcountSubarrays(nums,k,m);coutresultendl;return0;}