哈希算法题目：K 个不同整数的子数组

题目描述：
给定一个正整数数组 nums 和一个整数 k，返回 nums 中 "好子数组" 的数目。一个好子数组定义为该子数组中恰好有 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]。

解题过程：

1. 问题分析
   我们需要统计所有连续子数组中，恰好包含 k 个不同整数的子数组个数。暴力解法是枚举所有子数组，时间复杂度为 O(n²)，对于大数据量会超时。

2. 关键思路
   这个问题可以转化为两个滑动窗口问题的差值：

• 最多包含 k 个不同整数的子数组个数
• 最多包含 k-1 个不同整数的子数组个数
  恰好包含 k 个不同整数的子数组个数 = 最多包含 k 个不同整数的子数组个数 - 最多包含 k-1 个不同整数的子数组个数

3. 辅助函数：计算最多包含 k 个不同整数的子数组个数

def at_most_k_distinct(nums, k):
    if k == 0:
        return 0
    
    left = 0
    count = 0
    freq = {}  # 哈希表记录每个数字的出现频率
    
    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

4. 主函数实现

def subarrays_with_k_distinct(nums, k):
    # 恰好 k 个不同 = 最多 k 个不同 - 最多 k-1 个不同
    return at_most_k_distinct(nums, k) - at_most_k_distinct(nums, k - 1)

5. 示例分析
   以 nums = [1,2,1,2,3], k = 2 为例：

• 最多包含 2 个不同整数的子数组个数：21
• 最多包含 1 个不同整数的子数组个数：14
• 恰好包含 2 个不同整数的子数组个数：21 - 14 = 7

6. 复杂度分析

• 时间复杂度：O(n)，每个元素最多被访问两次
• 空间复杂度：O(k)，哈希表最多存储 k 个键值对

这种方法通过巧妙的数学转换，将复杂的确切计数问题转化为简单的区间计数问题，是滑动窗口与哈希表结合的经典应用。