Hard

题目描述

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

「好子数组」定义为：恰好包含 k 个不同整数的子数组。

例如，[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 * 10^4
  • 1 <= nums[i], k <= nums.length

解题思路

这是一道滑动窗口的经典题目。直接计算恰好包含 k 个不同整数的子数组比较困难，我们可以用转换思想：

核心思路： 恰好包含 k 个不同整数的子数组数量 = 最多包含 k 个不同整数的子数组数量 - 最多包含 (k-1) 个不同整数的子数组数量

具体步骤：

  1. 实现一个辅助函数 atMostK，计算最多包含 k 个不同整数的子数组数量
  2. 使用滑动窗口技术：维护一个窗口，用哈希表记录窗口内每个数字的出现次数
  3. 当窗口内不同整数个数超过 k 时，收缩左边界
  4. 每次右边界扩展时，以当前右边界为结尾的符合条件的子数组数量就是当前窗口长度

对于 atMostK 函数的实现：

  • 使用双指针 left 和 right 维护滑动窗口
  • 用哈希表统计窗口内不同数字的个数
  • 当不同数字个数超过 k 时，移动 left 指针直到满足条件
  • 每次移动 right 时，累加以 right 为结尾的合法子数组数量（即 right - left + 1）

最终答案就是 atMostK(nums, k) - atMostK(nums, k-1)。

代码实现

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return atMostK(nums, k) - atMostK(nums, k - 1);
    }
    
private:
    int atMostK(vector<int>& nums, int k) {
        if (k == 0) return 0;
        
        unordered_map<int, int> count;
        int left = 0, result = 0;
        
        for (int right = 0; right < nums.size(); right++) {
            if (count[nums[right]]++ == 0) {
                k--;
            }
            
            while (k < 0) {
                if (--count[nums[left]] == 0) {
                    k++;
                }
                left++;
            }
            
            result += right - left + 1;
        }
        
        return result;
    }
};

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        return self.atMostK(nums, k) - self.atMostK(nums, k - 1)
    
    def atMostK(self, nums: List[int], k: int) -> int:
        if k == 0:
            return 0
        
        count = {}
        left = 0
        result = 0
        
        for right in range(len(nums)):
            if nums[right] not in count:
                count[nums[right]] = 0
            count[nums[right]] += 1
            
            if count[nums[right]] == 1:
                k -= 1
            
            while k < 0:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    k += 1
                left += 1
            
            result += right - left + 1
        
        return result

public class Solution {
    public int SubarraysWithKDistinct(int[] nums, int k) {
        return AtMostK(nums, k) - AtMostK(nums, k - 1);
    }
    
    private int AtMostK(int[] nums, int k) {
        if (k == 0) return 0;
        
        Dictionary<int, int> count = new Dictionary<int, int>();
        int left = 0, result = 0;
        
        for (int right = 0; right < nums.Length; right++) {
            if (!count.ContainsKey(nums[right])) {
                count[nums[right]] = 0;
            }
            
            if (count[nums[right]]++ == 0) {
                k--;
            }
            
            while (k < 0) {
                if (--count[nums[left]] == 0) {
                    k++;
                }
                left++;
            }
            
            result += right - left + 1;
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraysWithKDistinct = function(nums, k) {
    function atMostK(nums, k) {
        let left = 0;
        let count = 0;
        let freq = new Map();
        
        for (let right = 0; right < nums.length; right++) {
            freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
            
            while (freq.size > k) {
                freq.set(nums[left], freq.get(nums[left]) - 1);
                if (freq.get(nums[left]) === 0) {
                    freq.delete(nums[left]);
                }
                left++;
            }
            
            count += right - left + 1;
        }
        
        return count;
    }
    
    return atMostK(nums, k) - atMostK(nums, k - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多被访问两次（一次添加到窗口，一次从窗口移除）
空间复杂度O(k)哈希表最多存储 k+1 个不同的元素

相关题目