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]

说明

• 子数组是数组中连续的一段。
• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i] <= nums.length
• 1 <= k <= nums.length

解题思路

直接枚举所有子数组会超时（O(n²)）。
核心思路：

1. 转化为两个前缀问题
   “恰好包含 k 个不同整数” = “最多包含 k 个不同整数” − “最多包含 k−1 个不同整数”。
2. 滑动窗口 + 哈希表计数
   用哈希表记录窗口内各数字出现次数，窗口右边界右移，左边界在“不同整数个数 > k”时收缩。
3. 计算最多包含 k 个不同整数的子数组数
   对于每个右边界，计算以该右边界结尾的符合条件的子数组数量。

逐步讲解

步骤 1：定义辅助函数

设函数 atMostK(nums, k) 返回数组 nums 中 最多包含 k 个不同整数 的子数组个数。

为什么用“最多”
因为“最多包含 k 个”可以通过滑动窗口高效计算，而“恰好 k 个”难以直接高效统计。

于是：

恰好 k 个 = atMostK(nums, k) − atMostK(nums, k−1)

步骤 2：实现 atMostK 函数

用滑动窗口维护一个区间 [left, right]，保证窗口内不同整数个数 ≤ k。

具体过程：

1. 初始化哈希表 freq 记录窗口内各数字出现次数，left = 0，count = 0（记录不同整数个数），result = 0。
2. 右指针 right 从 0 到 n-1 遍历：
   • 将 nums[right] 加入哈希表，如果加入前该数字次数为 0，则 count += 1。
   • 当 count > k 时，移动左指针 left，减少 nums[left] 的计数，如果减到 0，则 count -= 1，left += 1。
   • 关键计算：此时窗口 [left, right] 满足条件，那么以 right 结尾的符合条件的子数组个数为 (right − left + 1)。
     因为：
     • 固定右边界，左边界可以从 left 取到 right，这些子数组都满足“最多 k 个不同整数”。
     • 举例：窗口为 [1,2,1] 时，右边界在最后一个 1，左边界可取 0,1,2，对应子数组 [1,2,1]、[2,1]、[1] 都满足。
3. 累加这些数量到 result。

示例：nums = [1,2,1,2,3], k = 2

• right=0: freq={1:1}, count=1, left=0, 加 1 个。
• right=1: freq={1:1,2:1}, count=2, left=0, 加 2 个（[1,2]、[2]）。
• right=2: freq={1:2,2:1}, count=2, left=0, 加 3 个（[1,2,1]、[2,1]、[1]）。
• right=3: freq={1:2,2:2}, count=2, left=0, 加 4 个。
• right=4: 加入 3 → count=3 > k，移动 left 直到移除一个不同整数（移除 1 一次后还有 1，再移直到移除 2），最后 left=3，freq={2:1,3:1}, count=2，加 2 个（[2,3]、[3]）。
  总数 = 1+2+3+4+2 = 12。即 atMostK(nums, 2) = 12。

步骤 3：计算 atMostK(nums, k−1)

同样过程，k−1 = 1：
计算得 atMostK(nums, 1) = 5（子数组：每个单独元素 [1]、[2]、[1]、[2]、[3]）。

步骤 4：结果

恰好 k = 2 的子数组数 = 12 − 5 = 7。

代码实现（Python）

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

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

复杂度分析

• 时间复杂度：O(n)，因为 atMostK 函数中每个元素最多被左右指针各访问一次，调用两次。
• 空间复杂度：O(k)，哈希表最多存储 k+1 个键值对。

关键点总结

1. 转化思想：“恰好 k 个”转为“最多 k 个”减“最多 k−1 个”。
2. 滑动窗口：用哈希表维护窗口内数字频次，保证不同整数个数 ≤ k。
3. 计数技巧：固定右边界，符合条件的左边界范围长度即为以该右边界结尾的子数组数。

这种“前缀相减”配合滑动窗口的方法是处理“恰好 k 个”问题的常用技巧，你理解了吗？