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

福大大架构师每日一题

发布于 2026-06-29 14:16:24

360

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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)<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 <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++完整代码如下：

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

long long countSubarrays(const vector<int>& nums, int k, int m) {
    // 内部函数：统计满足 不同元素个数 >= distinctLimit 且
    // 出现次数 >= m 的元素个数 >= k 的子数组个数
    auto calc = [&](int distinctLimit) -> long long {
        unordered_map<int, int> 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<int> nums = {1, 2, 1, 2, 2};
    int k = 2, m = 2;
    long long result = countSubarrays(nums, k, m);
    cout << result << endl;
    return0;
}