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

约 5 分钟
文章信息 9 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 微软 美团 携程
标签
数组 哈希表 滑动窗口 计数

题目描述

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

image-20260928225500279

题意分析

给定整数数组，统计其中恰好包含 k 种不同整数的非空连续子数组数量。相同值在一个区间内出现多次仍只算一种，但不同下标区间即使内容相同，也需要分别计数。

要求的是所有符合条件的子数组个数，不是最长长度。直接维护“恰好 k 种”的窗口时，左侧重复值可能产生多个有效起点，计数不容易一次处理，可以转成两个“至多”条件作差。

解法：前缀计数差法与滑动窗口

核心思路

[!blue]

定义 atMost(t) 为不同整数种类不超过 t 的非空子数组数量。至多 k 种的集合，恰好由至多 k - 1 种与恰好 k 种组成，两部分互不重叠，所以答案为 atMost(k) - atMost(k - 1)。只需要正确实现一种上限计数方法。

在 atMost 中，用频次表维护闭区间 [left, right]。加入右端元素后，如果种类超过上限，就不断移出左端元素；某个值的频次降为零时才删除键，因为只移出一个副本未必会减少种类。

收缩到合法后，left 是当前右端下最靠左的可行起点。更早被排除的起点不能重新合法，因为右端继续扩大不会减少种类；更靠右的任何起点都合法，因为从一个合法区间删除前缀只会减少或保持种类。

因此，以当前 right 结尾的合法子数组，恰好对应从 left 到 right 的所有起点，共 right - left + 1 个。把这个数量累加到答案，就逐个结束位置统计了所有合法区间，不会漏掉短后缀，也不会让同一区间被重复计算。

两次 atMost 分别维护独立窗口，最后相减得到精确种类数。至多零种的非空子数组数量为零：Java 直接返回，Go 在上限为零时把每个窗口收缩为空，也得到相同计数。

解题步骤

  1. 分别计算 atMost(k) 和 atMost(k - 1)，返回两者之差。
  2. 每次计数初始化空频次表、左端和累计数量。
  3. 向窗口加入右端元素；种类超限时持续缩左端，频次归零就删键。
  4. 窗口合法后，将 right - left + 1 加入累计数量。
  5. 处理完全部右端，返回当前上限下的子数组总数。

代码实现

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    private int atMost(int[] nums, int k) {
        if (k <= 0) {
            return 0;
        }

        Map<Integer, Integer> count = new HashMap<>();
        int left = 0;
        int answer = 0;

        for (int right = 0; right < nums.length; right++) {
            count.put(nums[right], count.getOrDefault(nums[right], 0) + 1);

            while (count.size() > k) {
                count.put(nums[left], count.get(nums[left]) - 1);

                if (count.get(nums[left]) == 0) {
                    // 最后一个副本离开窗口时，种类才减少。
                    count.remove(nums[left]);
                }

                left++;
            }

            // 合法窗口内每个起点都对应一个以当前右端结尾的子数组。
            answer += right - left + 1;
        }

        return answer;
    }
}

func subarraysWithKDistinct(nums []int, k int) int {
    if k <= 0 {
        return 0
    }
    return atMost(nums, k) - atMost(nums, k-1)
}

func atMost(nums []int, k int) int {
    count := make(map[int]int)
    left := 0
    answer := 0

    for right, v := range nums {
        count[v]++
        for len(count) > k {
            count[nums[left]]--
            if count[nums[left]] == 0 {
                // 最后一个副本离开窗口时，种类才减少。
                delete(count, nums[left])
            }
            left++
        }
        // 合法窗口内每个起点都对应一个以当前右端结尾的子数组。
        answer += right - left + 1
    }

    return answer
}

复杂度分析

  • 时间复杂度：期望 $O(n)$。两次扫描各自的左右指针都只向右移动，哈希表单次操作期望为常量时间。
  • 空间复杂度：$O(\min(n, k + 1))$，包括加入新种类但尚未收缩的瞬间；两个计数过程依次执行，不需要同时保存两份历史窗口。

关键点总结

[!green]

  • 按种类上限的累计数量作差，把“恰好”转换为适合滑动窗口的“至多”。
  • 每个右端的贡献是合法起点数，而不是只增加一个或只更新最长窗口。
  • 频次表的键数表示种类数，副本数量决定什么时候才能删键。

易错点总结

[!yellow]

  • 用集合代替频次表，无法知道移出一个值后窗口中是否还留有同值副本。
  • 超限时只移动左端一次，可能还没有移出某种值的最后一个副本，窗口仍非法。
  • 在窗口恢复合法前计数，会把超过种类限制的区间算入。
  • 每个右端只加一，会漏掉同一合法窗口中不同起点形成的全部后缀子数组。
  • 直接对恰好条件套用“窗口长度即贡献”，会把种类少于 k 的后缀也算进去，需通过两次至多计数相减排除。

相似题目

题目 难度 关联与区别
340. 至多包含 K 个不同字符的最长子串 中等 窗口状态同样是不同元素种数，本题按合法起点数量计数，而不是只取最长长度。
930. 和相同的二元子数组 中等 同样可用两个至多阈值的计数相减得到恰好条件，本题阈值是种类数，原题是二元数组和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/87604932
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！