哈希算法题目：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]

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

题目解析

1. 问题理解

• 子数组必须是原数组中连续的一段，不能跳过中间元素。
• 我们需要统计所有恰好包含 k 个不同整数的子数组个数。
• 如果直接暴力枚举所有子数组，复杂度为 O(n²)，在数组较大时（如 n=10^5）会超时，因此需要更优的方法。

2. 关键思路

这个问题可以用 滑动窗口 + 哈希表 来高效解决。但要注意：

• 如果直接统计“恰好包含 k 个不同整数的子数组”数量，滑动窗口不容易直接得出结果。
• 常用的技巧是：
  恰好包含 k 个不同整数的子数组数量 = 包含最多 k 个不同整数的子数组数量 − 包含最多 k−1 个不同整数的子数组数量

为什么这个转换成立？
定义函数 atMostK(nums, k) 表示“数组中最多包含 k 个不同整数的子数组个数”。
那么“恰好包含 k 个不同整数的子数组个数” = atMostK(nums, k) − atMostK(nums, k−1)
因为“最多包含 k 个”包含了“包含 0,1,2,...,k 个”的情况，减去“最多包含 k-1 个”就剩下“恰好包含 k 个”的情况。

这样，我们就把原问题转化为了 计算“最多包含 k 个不同整数的子数组个数” 的问题，而这个问题可以用滑动窗口高效求解。

3. 滑动窗口求解 atMostK(nums, k)

目标：计算数组中有多少个子数组，其包含的不同整数个数 ≤ k。
方法：

1. 使用两个指针 left 和 right 表示滑动窗口的左右边界，初始都指向数组起始位置。
2. 使用哈希表（如字典或哈希映射）记录窗口内每个整数出现的次数。
3. 右指针 right 不断向右移动，将 nums[right] 加入窗口，更新哈希表计数。
4. 如果窗口内不同整数个数 > k，则移动左指针 left 向右收缩窗口，直到不同整数个数 ≤ k。每次左指针移动时，减少哈希表中对应整数的计数，如果计数减到 0，则从哈希表中移除该整数。
5. 在每一步右指针移动后，窗口 [left, right] 满足“最多包含 k 个不同整数”，那么以 right 结尾的符合条件的子数组个数 = right − left + 1。累加这个值即可。

为什么以 right 结尾的子数组个数是 right − left + 1？
因为当窗口 [left, right] 满足条件时，所有左边界在 [left, right] 范围内、右边界固定在 right 的子数组都满足“最多 k 个不同整数”。这样的左边界有 right − left + 1 种选择。

示例：nums = [1,2,1,2,3], k=2
右指针移动过程：

• right=0, window=[1], cnt={1:1}, left=0, 不同整数=1 ≤ k，以 right 结尾的子数组：[1] → 1 个
• right=1, window=[1,2], cnt={1:1,2:1}, 不同整数=2 ≤ k，以 right 结尾的子数组：[2], [1,2] → 2 个
• right=2, window=[1,2,1], cnt={1:2,2:1}, 不同整数=2 ≤ k，以 right 结尾的子数组：[1], [2,1], [1,2,1] → 3 个
• right=3, window=[1,2,1,2], cnt={1:2,2:2}, 不同整数=2 ≤ k，以 right 结尾的子数组：[2], [1,2], [2,1,2], [1,2,1,2] → 4 个
• right=4, window=[1,2,1,2,3], cnt 中不同整数=3 > k，移动 left 直到不同整数 ≤ 2：
  left 移到 2, window=[1,2,3], cnt={1:1,2:1,3:1} 仍然 3>k，left 再移到 3, window=[2,3], cnt={2:1,3:1} 不同整数=2 ≤ k，此时以 right=4 结尾的子数组：左边界从 3 到 4，共 2 个：[3], [2,3]
  累加：1+2+3+4+2 = 12，即 atMostK(nums, 2) = 12。

同理 atMostK(nums, 1) = 5（可自行验证）。
恰好包含 2 个不同整数的子数组数 = 12 − 5 = 7，与示例一致。

4. 算法步骤

1. 实现函数 atMostK(nums, k)：
   • 初始化 left=0, 哈希表 count={}, result=0
   • 遍历 right 从 0 到 n-1：
     • 将 nums[right] 加入 count
     • 当 count 中不同整数个数 > k：
       • 减少 nums[left] 在 count 中的计数
       • 如果计数为 0，从 count 中删除该键
       • left 右移一位
     • 累加 (right − left + 1) 到 result
   • 返回 result
2. 最终结果 = atMostK(nums, k) − atMostK(nums, k−1)
3. 注意：如果 k=0，则直接返回 0（因为不可能有“恰好 0 个不同整数”的非空子数组）

5. 复杂度分析

• 时间复杂度：O(n)，因为左右指针各遍历数组一次，每个元素被加入和移除哈希表各一次。
• 空间复杂度：O(k)，哈希表最多存储 k+1 个键值对（在 atMostK 函数中）。

6. 代码实现（Python示例）

def subarraysWithKDistinct(nums, k):
    def atMostK(nums, k):
        count = {}
        left = 0
        res = 0
        for right, num in enumerate(nums):
            count[num] = count.get(num, 0) + 1
            while len(count) > k:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    del count[nums[left]]
                left += 1
            res += right - left + 1
        return res
    
    if k == 0:
        return 0
    return atMostK(nums, k) - atMostK(nums, k - 1)

# 测试
print(subarraysWithKDistinct([1,2,1,2,3], 2))  # 输出 7

总结

本题核心是利用 滑动窗口 高效计算“最多包含 k 个不同整数的子数组个数”，再通过 差值转换 得到“恰好包含 k 个不同整数的子数组个数”。哈希表用于实时维护窗口内不同整数的计数。这种方法避免了直接枚举所有子数组，将时间复杂度优化到 O(n)，是一种经典的“哈希 + 双指针”结合的应用。