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

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。

解释：

满足条件的子数组为：

子数组

不同整数

频率

[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(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)。
所有起点在 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 <3，全程不会触发窗口收缩逻辑，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完整代码如下：

package main

 import (
    "fmt"
)

 func countSubarrays(nums []int, k, m int)int64 {
    calc := func(distinctLimit int) (ans int64) {
        cnt := map[int]int{}
        geM := 0// 窗口中的出现次数 >= m 的元素个数
        left := 0
        for _, x := range nums {
            // 1. 入
            cnt[x]++
            if cnt[x] == m {
                geM++
            }

             // 2. 出
            forlen(cnt) >= distinctLimit && geM >= k {
                out := nums[left]
                if cnt[out] == m {
                    geM--
                }
                cnt[out]--
                if cnt[out] == 0 {
                    delete(cnt, out)
                }
                left++
            }

             // 3. 更新答案
            ans += int64(left)
        }
        return
    }

     return calc(k) - calc(k+1)
}

 func main() {
    nums := []int{1, 2, 1, 2, 2}
    k := 2
    m := 2
    result := countSubarrays(nums, k, m)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List

 def countSubarrays(nums: List[int], k: int, m: int) -> int:
    # 内部函数：统计满足 不同元素个数 >= distinctLimit 且
    # 出现次数 >= m 的元素个数 >= k 的子数组个数
    def calc(distinctLimit: int) -> int:
        cnt = {}          # 当前窗口中各元素的出现次数
        geM = 0           # 出现次数 >= m 的元素个数
        left = 0
        ans = 0

         for x in nums:
            # 1. 将右端点元素加入窗口
            cnt[x] = cnt.get(x, 0) + 1
            if cnt[x] == m:
                geM += 1

             # 2. 当窗口满足条件时，收缩左边界直到条件不再满足
            while len(cnt) >= distinctLimit and geM >= k:
                out = nums[left]
                if cnt[out] == m:
                    geM -= 1
                cnt[out] -= 1
                if cnt[out] == 0:
                    del cnt[out]
                left += 1

             # 3. 对于当前右端点，所有左端点 < left 的子数组均满足条件
            ans += left

         return ans

     # 容斥：不同元素个数恰好为 k，且每个元素的出现次数都 >= m
    return calc(k) - calc(k + 1)

 if __name__ == "__main__":
    nums = [1, 2, 1, 2, 2]
    k = 2
    m = 2
    result = countSubarrays(nums, k, m)
    print(result) 

C++完整代码如下：

  

  

  


 using namespace std;

 long long countSubarrays(const vector& nums, int k, int m) {
    // 内部函数：统计满足 不同元素个数 >= distinctLimit 且
    // 出现次数 >= m 的元素个数 >= k 的子数组个数
    auto calc = [&](int distinctLimit) -> long long {
        unordered_map cnt;
        int geM = 0;          // 出现次数 >= m 的元素个数
        int left = 0;
        long long ans = 0;

         for (int x : nums) {
            // 1. 将右端点元素加入窗口
            cnt[x]++;
            if (cnt[x] == m) {
                geM++;
            }

             // 2. 当窗口满足条件时，收缩左边界直到条件不再满足
            while ((int)cnt.size() >= distinctLimit && geM >= k) {
                int out = nums[left];
                if (cnt[out] == m) {
                    geM--;
                }
                cnt[out]--;
                if (cnt[out] == 0) {
                    cnt.erase(out);
                }
                left++;
            }

             // 3. 对于当前右端点，所有左端点 < left 的子数组均满足条件
            ans += left;
        }
        return ans;
    };

     // 容斥：不同元素个数恰好为 k，且每个元素的出现次数都 >= m
    return calc(k) - calc(k + 1);
}

 int main() {
    vector nums = {1, 2, 1, 2, 2};
    int k = 2, m = 2;
    long long result = countSubarrays(nums, k, m);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。