992. K 个不同整数的子数组

Difficulty
Medium
Tags
滑动窗口
URL
https://leetcode.cn/problems/subarrays-with-k-different-integers/
Star
给定一个正整数数组 nums和一个整数 k ，返回 num 中 「好子数组」 的数目。
如果 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
通过次数26,916提交次数58,000

滑动窗口

思路
限定了只能包含 k 个不同的整数。如果是不超过 k 个不同的整数，那么按照常规的滑动窗口，每次新来一个元素，缩减窗口（如果有必要）后，再 res += r-l ，即以新来的元素为子数字末尾，计算新增的子数字个数。
但是现在是要窗口内不同的数字正好为k个，那么可以计算出 最多k 种整数的子数组个数 最多k-1种整数的子数组个数
题解
class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        return self.helper(nums, k) - self.helper(nums, k-1)
    
    def helper(self, nums, k):
        """找最大窗口，该窗口内最多有K种数字
        """
        l, r = 0, 0
        wds = collections.defaultdict(int)
        res = 0
        while r < len(nums):
            wds[nums[r]] += 1
            r += 1
            while len(wds) > k:
                wds[nums[l]] -= 1
                if wds[nums[l]] == 0:
                    del wds[nums[l]]
                l += 1
            res += r-l

        return res