Hard

题目描述

给你一个整数数组 nums 和两个整数 k 和 m。

返回一个整数，表示 nums 中满足以下条件的子数组个数：

  • 子数组包含恰好 k 个不同的整数
  • 在子数组中，每个不同的整数至少出现 m 次

示例 1：

输入：nums = [1,2,1,2,2], k = 2, m = 2
输出：2
解释：
满足条件的子数组（k = 2 个不同整数，每个至少出现 m = 2 次）：
- [1, 2, 1, 2]：{1, 2} → 2 个不同数字，频次 {1: 2, 2: 2}
- [1, 2, 1, 2, 2]：{1, 2} → 2 个不同数字，频次 {1: 2, 2: 3}

示例 2：

输入：nums = [3,1,2,4], k = 2, m = 1
输出：3
解释：
满足条件的子数组（k = 2 个不同整数，每个至少出现 m = 1 次）：
- [3, 1]：{3, 1} → 2 个不同数字，频次 {3: 1, 1: 1}
- [1, 2]：{1, 2} → 2 个不同数字，频次 {1: 1, 2: 1}
- [2, 4]：{2, 4} → 2 个不同数字，频次 {2: 1, 4: 1}

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= k, m <= nums.length

解题思路

这是一道经典的滑动窗口问题，需要巧妙运用"恰好K个"转化为"至多K个"的思想。

核心思路： 恰好含有K个不同整数的子数组个数 = 至多含有K个不同整数的子数组个数 - 至多含有(K-1)个不同整数的子数组个数

算法步骤：

  1. 实现 atMost(k) 函数：计算至多包含k个不同整数且每个整数至少出现m次的子数组个数

    • 使用滑动窗口技术，维护一个哈希表记录当前窗口中每个数字的出现次数
    • 当窗口中不同数字个数超过k时，收缩左边界
    • 当所有数字的出现次数都至少为m时，累加以当前右边界结尾的有效子数组个数

  2. 处理频次约束：

    • 除了控制不同数字个数，还需确保每个数字在窗口中至少出现m次
    • 使用 validCount 记录满足频次要求的不同数字个数
    • 只有当 validCount == distinctCount 且 distinctCount <= k 时才计算贡献

  3. 最终答案：atMost(k) - atMost(k-1)

时间复杂度优化要点：

  • 双指针技术保证每个元素最多被访问两次
  • 哈希表操作均为O(1)

代码实现

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

class Solution:
    def countSubarrays(self, nums: list[int], k: int, m: int) -> int:
        return self.atMost(nums, k, m) - self.atMost(nums, k - 1, m)
    
    def atMost(self, nums: list[int], k: int, m: int) -> int:
        if k <= 0:
            return 0
        
        count = {}
        left = 0
        valid_count = 0
        result = 0
        
        for right in range(len(nums)):
            count[nums[right]] = count.get(nums[right], 0) + 1
            if count[nums[right]] == m:
                valid_count += 1
            
            while len(count) > k or (valid_count > 0 and valid_count < len(count)):
                if count[nums[left]] == m:
                    valid_count -= 1
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    del count[nums[left]]
                left += 1
            
            if valid_count == len(count):
                result += right - left + 1
        
        return result

public class Solution {
    public long CountSubarrays(int[] nums, int k, int m) {
        return AtMost(nums, k, m) - AtMost(nums, k - 1, m);
    }
    
    private long AtMost(int[] nums, int k, int m) {
        if (k <= 0) return 0;
        
        Dictionary<int, int> count = new Dictionary<int, int>();
        int left = 0, validCount = 0;
        long result = 0;
        
        for (int right = 0; right < nums.Length; right++) {
            count[nums[right]] = count.GetValueOrDefault(nums[right], 0) + 1;
            if (count[nums[right]] == m) {
                validCount++;
            }
            
            while (count.Count > k || (validCount > 0 && validCount < count.Count)) {
                if (count[nums[left]] == m) {
                    validCount--;
                }
                count[nums[left]]--;
                if (count[nums[left]] == 0) {
                    count.Remove(nums[left]);
                }
                left++;
            }
            
            if (validCount == count.Count) {
                result += right - left + 1;
            }
        }
        
        return result;
    }
}

var countSubarrays = function(nums, k, m) {
    const n = nums.length;
    let count = 0;
    
    for (let i = 0; i < n; i++) {
        const freq = new Map();
        let distinctCount = 0;
        
        for (let j = i; j < n; j++) {
            if (!freq.has(nums[j])) {
                freq.set(nums[j], 0);
                distinctCount++;
            }
            freq.set(nums[j], freq.get(nums[j]) + 1);
            
            if (distinctCount === k) {
                let validSubarray = true;
                for (const [num, count] of freq) {
                    if (count < m) {
                        validSubarray = false;
                        break;
                    }
                }
                if (validSubarray) {
                    count++;
                }
            } else if (distinctCount > k) {
                break;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中n是数组长度。双指针技术保证每个元素最多被访问两次
空间复杂度O(min(n, k))，哈希表最多存储k个不同元素的计数信息