恰好 K 个不同整数的子数组个数

题目描述
给你一个整数数组 nums 和一个整数 k，你需要统计并返回该数组中“恰好包含 k 个不同整数”的连续子数组的个数。

示例 1：
输入：nums = [1,2,1,2,3], k = 2
输出：7
解释：恰好包含 2 个不同整数的子数组有：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]。

注意：子数组是数组中连续的一段。

解题思路
这是一个经典的滑动窗口结合前缀和思想的线性动态规划（或双指针）问题。直接统计“恰好” k 个不同整数比较困难，但我们可以转化为“最多” k 个不同整数的子数组个数，减去“最多” k-1 个不同整数的子数组个数，这样差就是“恰好” k 个的个数。
核心思路：

• 定义函数 atMostK(nums, K)，返回数组 nums 中“最多包含 K 个不同整数”的连续子数组个数。
• 那么答案 = atMostK(nums, k) - atMostK(nums, k-1)。

现在我们重点讲解如何实现 atMostK 函数。

第一步：实现 atMostK 函数
我们可以用滑动窗口（双指针）来统计。
算法步骤：

1. 初始化一个哈希表（或数组，因为整数范围可能有限，但用哈希表更通用）freq 来记录当前窗口内每个整数的出现次数。
2. 初始化左指针 left = 0，右指针 right 从 0 开始遍历数组。
3. 对于每个右指针位置 right，将 nums[right] 加入窗口（freq 中对应计数加 1）。
4. 如果加入后，窗口内不同整数的个数（即 freq 的大小）超过了 K，则需要移动左指针缩小窗口，直到不同整数个数 ≤ K。具体做法是：每次将 nums[left] 从 freq 中计数减 1，如果减到 0，则从 freq 中删除这个键，然后 left 右移一位。
5. 对于当前右指针位置，以 right 结尾的、且满足“最多 K 个不同整数”的子数组个数，就是从 left 到 right 的所有连续子数组（结尾都是 right），即 right - left + 1 个。我们累加这个值。
6. 遍历完所有 right，累加值就是 atMostK 的返回值。

为什么是 right - left + 1 个？
因为当窗口 [left, right] 满足条件时，它的任何以 right 结尾的子数组（即起始点从 left 到 right 的任意位置）都满足“最多 K 个不同整数”。这样的子数组数量正好是窗口长度。

第二步：计算恰好 k 个不同整数的子数组个数
根据第一步得到的 atMostK 函数，我们可以计算：

• totalAtMostK = atMostK(nums, k) // 最多 k 个不同整数的子数组个数
• totalAtMostKMinus1 = atMostK(nums, k-1) // 最多 k-1 个不同整数的子数组个数
• 答案 = totalAtMostK - totalAtMostKMinus1

第三步：边界情况
如果 k = 0，atMostK(nums, -1) 无意义，但“恰好 0 个不同整数”意味着子数组为空，而题目中连续子数组通常非空，所以这种情况返回 0。我们可以特判：如果 k = 0，直接返回 0。
另外，如果 k 大于数组中不同整数的总数，则“恰好 k 个”的子数组个数也为 0。

第四步：复杂度分析

• 时间复杂度：O(n)，因为每个元素最多被左指针和右指针各访问一次。
• 空间复杂度：O(n)，用于哈希表存储窗口内数字的频率。

第五步：举例说明
以 nums = [1,2,1,2,3], k = 2 为例：

1. 计算 atMostK(nums, 2)：

   • 右指针遍历，窗口变化及累加值：
     right=0: 窗口[1], 不同整数=1, 累加1
     right=1: 窗口[1,2], 不同整数=2, 累加2
     right=2: 窗口[1,2,1], 不同整数=2, 累加3
     right=3: 窗口[1,2,1,2], 不同整数=2, 累加4
     right=4: 加入3后不同整数变为3>2，左指针移动直到删除1（计数从2减为1），窗口变为[2,1,2,3]，不同整数=3>2，继续左移删除2（计数从2减为1），窗口变为[1,2,3]，不同整数=3>2，继续左移删除1（计数从1减为0），窗口变为[2,3]，不同整数=2，累加2（窗口长度）
     累计总和 = 1+2+3+4+2 = 12
     所以 atMostK(nums,2) = 12

2. 计算 atMostK(nums, 1)：

   • 类似过程，最后得到总和 = 5（子数组：[1], [2], [1], [2], [3] 各一个，但注意连续相同数字的多个子数组也算，比如 [1,1] 是不存在的，因为数组没有连续相同数字。详细计算略，结果是 5）

3. 答案 = 12 - 5 = 7，与示例一致。

第六步：代码实现（伪代码）

def subarraysWithKDistinct(nums, k):
    if k == 0:
        return 0
    
    def atMostK(K):
        left = 0
        freq = {}
        count = 0
        for right in range(len(nums)):
            # 加入右指针数字
            freq[nums[right]] = freq.get(nums[right], 0) + 1
            # 如果不同整数个数超过K，移动左指针
            while len(freq) > K:
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    del freq[nums[left]]
                left += 1
            # 累加以right结尾的满足条件的子数组个数
            count += right - left + 1
        return count
    
    return atMostK(k) - atMostK(k-1)

总结
这道题的核心技巧是“恰好”转化为“最多”的差值计算，再用滑动窗口高效计算“最多”的情况。滑动窗口保证了线性时间复杂度，是一种常见的线性动态规划思想的应用。