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

题目描述：
给定一个正整数数组 nums 和一个整数 k，你需要统计数组中连续子数组的个数，其中恰好包含 k 个不同的整数。

示例：
输入：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]。

解题思路：

这个问题可以转化为两个“最多包含”问题的差值。
定义：

• atMostK(k)：表示最多包含 k 个不同整数的子数组个数。
  那么恰好包含 k 个不同整数的子数组个数 = atMostK(k) - atMostK(k-1)。

为什么？
因为“恰好 k 个” = “最多 k 个” − “最多 k−1 个”。

步骤分解：

1. 如何计算 atMostK(k)？

我们可以使用滑动窗口（双指针）来统计：

• 维护一个窗口 [left, right]，用哈希表（或数组，若数值范围已知）记录窗口内每个数字的出现次数。
• 当窗口中不同整数的个数 distinct > k 时，移动左指针 left，直到 distinct ≤ k。
• 对于每个右指针位置 right，以 right 为结尾的子数组中，满足条件的子数组个数为 right - left + 1（即窗口长度）。
  为什么？
  因为对于固定的 right，左端点可以从 left 取到 right，这些子数组都满足“最多 k 个不同整数”。

伪代码：

function atMostK(nums, k):
    left = 0
    freq = {}  # 记录窗口内数字出现次数
    distinct = 0
    count = 0
    for right from 0 to n-1:
        # 加入 nums[right]
        freq[nums[right]] += 1
        if freq[nums[right]] == 1: distinct += 1
        # 如果不同整数超过 k，收缩左边界
        while distinct > k:
            freq[nums[left]] -= 1
            if freq[nums[left]] == 0: distinct -= 1
            left += 1
        # 累加以 right 结尾的满足条件的子数组个数
        count += (right - left + 1)
    return count

示例运行（nums = [1,2,1,2,3], k=2）：
atMostK(2) = 12，atMostK(1) = 5
恰好 2 个不同的子数组个数 = 12 − 5 = 7。

2. 为什么滑动窗口方法适用于 atMostK(k)？

• 当右指针右移时，不同整数数可能增加，左指针只会右移（不会左移），因此每个元素至多被加入和移除一次，时间复杂度为 O(n)。
• 对于每个右指针，我们找到最小的左指针 left，使得窗口内不同整数 ≤ k。此时窗口内所有子数组都满足条件，且以 right 结尾的满足条件的子数组个数正好是窗口长度。

3. 完整算法流程：

1. 实现辅助函数 atMostK(k)，使用滑动窗口计算最多包含 k 个不同整数的子数组个数。
2. 最终答案 = atMostK(k) - atMostK(k-1)。

边界情况：

• 如果 k == 0？根据定义，恰好 0 个不同整数的子数组不存在（除非数组为空，但通常题目中数组非空），所以结果为 0。
• 如果 k 大于数组中不同整数的总数？那么结果为 0，因为不可能有恰好 k 个不同的整数。

代码实现（Python）：

def subarraysWithKDistinct(nums, k):
    def atMostK(K):
        from collections import defaultdict
        freq = defaultdict(int)
        left = 0
        distinct = 0
        count = 0
        for right in range(len(nums)):
            # 加入右指针指向的元素
            if freq[nums[right]] == 0:
                distinct += 1
            freq[nums[right]] += 1
            # 如果不同整数超过 K，移动左指针
            while distinct > K:
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    distinct -= 1
                left += 1
            # 累加以 right 结尾的子数组个数
            count += (right - left + 1)
        return count
    
    return atMostK(k) - atMostK(k - 1)

复杂度分析：

• 时间复杂度：O(n)，因为每个元素最多被加入窗口一次、移除窗口一次。
• 空间复杂度：O(n)，用于存储哈希表记录数字频率。

总结：

这个问题的关键在于将“恰好 k 个”转化为“最多 k 个”与“最多 k−1 个”的差值，从而利用滑动窗口高效计算。
滑动窗口用于求“最多 k 个”时，通过维护窗口内不同整数的个数，可以在 O(n) 时间内得到结果。
这是一种常见的技巧，适用于许多“恰好 k 个”的计数问题。