0992：K 个不同整数的子数组（2210 分）

力扣第 123 场周赛第 4 题

题目

给定一个正整数数组 nums和一个整数 k，返回 nums 中 「好子数组」 的数目。

如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。

• 例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。

子数组 是数组的 连续 部分。

示例 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 <= nums.length <= 2 * 104
• 1 <= nums[i], k <= nums.length

相似问题：

• 0003：无重复字符的最长子串
• 0159：至多包含两个不同字符的最长子串
• 0340：至多包含 K 个不同字符的最长子串
• 2062：统计字符串中的元音子字符串（1458 分）
• 2107：分享 K 个糖果后独特口味的数量
• 2261：含最多 K 个可整除元素的子数组（1724 分）
• 2799：统计完全子数组的数目（1397 分）

分析

• 恰好型窗口计数的一种常用方法是转为两个至多/少型窗口计数的差
• 本题可以求 f(k) 代表最多 k 个不同整数的子数组个数，用滑动窗口容易求解
• 答案即是 f(k)-f(k-1)

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        def cal(k):
            res, i, ct = 0,0, defaultdict(int)
            for j,x in enumerate(nums):
                ct[x] += 1
                while len(ct)>k:
                    ct[nums[i]] -= 1
                    if not ct[nums[i]]:
                        del ct[nums[i]]
                    i += 1
                res += j-i+1
            return res

        return cal(k)-cal(k-1)

154 ms