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

2026-05-22 HGNULB 约 11 分钟

文章信息 9 个分类 4 个标签

分类

题目描述

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

题意分析

给整数数组 nums 和整数 k，统计有多少个连续子数组，其中不同整数的种类数恰好等于 k。返回个数，不用返回具体子数组。

「连续」意味着子数组由一对下标 (left, right) 唯一确定，候选总数是 $O(n^2)$；「恰好」是本题的全部难度所在。约束里 nums 长度到 $2 \times 10^4$，$O(n^2)$ 的枚举约 $4 \times 10^8$ 次基本操作，卡在超时边缘且每次还要维护种类数，实际必挂，所以目标是线性或接近线性。

另一条信号是 1 <= nums[i] <= nums.length，值域被限制在数组长度以内。这暗示计数结构可以用定长数组代替哈希表（虽然本文的实现用了哈希表，写法更通用）。

真正要盯住的是「恰好」和「至多」的差别。窗口内不同整数的种类数关于窗口区间是单调的：把窗口缩小，种类数只会减少或不变。「至多 k 种」因此具有一个漂亮性质——若 [left, right] 至多 k 种，则它的任意子区间也至多 k 种，这条性质让双指针的左边界可以只增不减。而「恰好 k 种」没有这个性质：缩小窗口会从「恰好 k」掉成「k-1」，再缩回来又是「恰好 k」，合法左边界是一段区间而不是一个点。这就是为什么本题被评为困难，而 340 题那样的「至多 k 种」只是中等。

边界：k 可能等于 1；k 可能大于数组中实际的种类数，此时答案为 0；数组元素可以大量重复。

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

核心思路

暴力是固定左端点向右扩，用哈希表维护种类数，一旦超过 k 就断开，$O(n^2)$ 时间，规模 $2 \times 10^4$ 下超时。

想上滑动窗口，第一反应是「对每个 right，找出使 [left, right] 恰好 k 种的 left」。写下去就会卡住：以 nums = [1,2,1,2,3]、k = 2 为例，当 right = 3 时，[0,3] = [1,2,1,2]、[1,3] = [2,1,2]、[2,3] = [1,2] 都恰好 2 种，而 [3,3] = [2] 只有 1 种。合法的 left 是区间 [0, 2]，需要两个边界（最小合法 left 和最大合法 left）才能数清楚。单个左指针只能记住一端，这就是「恰好」不能直接滑窗的根本原因。

瓶颈找到了：难的不是滑窗，是「恰好」这个双边约束。而「至多 k 种」是单边约束，天然适配滑窗——对每个 right，存在唯一的最小 left，使得 [left, right] 至多 k 种，且 left 随 right 单调不减（右端加入新元素只会让种类数变多或不变，左边界不可能需要回退）。

由此得到关键观察，一条集合上的恒等式：

$exactly(k) = atMost(k) - atMost(k-1)$

「不同整数个数至多 k 个」的子数组集合，减去「至多 k-1 个」的子数组集合，剩下的正是「恰好 k 个」的那些。因为后者是前者的真子集，两个集合的差集就是种类数严格等于 k 的部分，计数直接相减即可。一个双边约束被拆成了两个单边约束。

于是只需实现 atMost(nums, k)。它的循环不变量是：每轮循环体结束时，[left, right] 是以 right 为右端点、不同整数不超过 k 种的最长窗口。为了维持它，右端加入 nums[right] 之后，只要种类数超标就从左边弹出元素，直到重新满足约束。

由不变量可以直接数出以 right 结尾的合法子数组个数：由于缩小窗口不会增加种类数，[left, right]、[left+1, right]、…、[right, right] 全部满足「至多 k 种」，而 [left-1, right] 已经超标（否则 left 还能更小），所以答案恰好是 right - left + 1 个，一个不多一个不少。把每个 right 的贡献累加起来，就是全部至多 k 种的子数组个数。

用哈希表 count 维护窗口内每个值的出现次数，count 的键数就是种类数。次数减到 0 时必须把键删掉，否则键数不减，种类数的度量就失真了。

解题步骤

主函数返回 atMost(nums, k) - atMost(nums, k - 1)：两次独立的线性扫描，每次用全新的哈希表和指针，不能共用状态。

atMost 中处理 k <= 0：Java 版直接短路返回 0——至多 0 种的非空子数组不存在，个数为 0。Go 版不写这个分支也对：加入元素后 len(count) > 0 必然成立，收缩会把窗口清空，left 变成 right + 1，right - left + 1 恰好是 0。注意「空子数组」不在统计范围内，这个函数在 k = 0 时应当返回 0 而不是 1。

初始化：count 为空表，left = 0，answer = 0。

右指针遍历，先加入：count[nums[right]]++。必须先把新元素纳入窗口再判断是否超标，顺序反了就会漏掉当前元素带来的新种类。

收缩用 while 而非 if：判断条件是 count 的键数是否大于 k。加入一个元素最多让种类数加 1，理论上一次收缩就能修好，但收缩过程中弹出的元素可能次数不为 0（重复元素），一次弹出未必减少种类数，所以必须循环到条件不再成立。

收缩时删键：count[nums[left]]--，减到 0 就把这个键从表中移除，然后 left++。删键这一步是种类数计量的生命线。

累加贡献：answer += right - left + 1。这一行必须放在收缩之后——收缩前窗口可能还超标，此时的 left 不满足不变量，算出来的是错的。

返回 answer。

以 nums = [1,2,1,2,3]、k = 2 走一遍，正确答案是 7。

先算 atMost(2)：
right = 0，加入 1，count = {1:1}，键数 1 不超标，answer += 0-0+1 = 1，累计 1。
right = 1，加入 2，count = {1:1, 2:1}，键数 2 不超标，answer += 1-0+1 = 2，累计 3。
right = 2，加入 1，count = {1:2, 2:1}，键数仍是 2，answer += 2-0+1 = 3，累计 6。
right = 3，加入 2，count = {1:2, 2:2}，键数 2，answer += 3-0+1 = 4，累计 10。
right = 4，加入 3，count = {1:2, 2:2, 3:1}，键数 3 超标，开始收缩：弹出 nums[0] = 1，次数降为 1 不删键，键数仍是 3，left = 1；再弹出 nums[1] = 2，次数降为 1 不删键，键数仍是 3，left = 2；再弹出 nums[2] = 1，次数降为 0，删键，键数变成 2，退出循环，left = 3。answer += 4-3+1 = 2，累计 12。
所以 atMost(2) = 12。这里连续弹了三次才修好窗口，正是 while 不能写成 if 的现场演示。

再算 atMost(1)：
right = 0，count = {1:1}，键数 1，answer += 1，累计 1。
right = 1，加入 2 后键数 2 超标，弹出 nums[0] = 1 并删键，left = 1，answer += 1-1+1 = 1，累计 2。
right = 2，加入 1 后键数 2 超标，弹出 nums[1] = 2 并删键，left = 2，answer += 1，累计 3。
right = 3，加入 2 后超标，弹出 nums[2] = 1 并删键，left = 3，answer += 1，累计 4。
right = 4，加入 3 后超标，弹出 nums[3] = 2 并删键，left = 4，answer += 1，累计 5。
所以 atMost(1) = 5。

最终答案 12 - 5 = 7。手工核对一下这 7 个：[1,2]、[2,1]、[1,2]（下标 2~3）、[1,2,1]、[2,1,2]、[1,2,1,2]、[2,3]，正好 7 个，与计算一致。

代码实现

class Solution {
    // 利用恒等式 exactly(k) = atMost(k) - atMost(k-1)，问题变成两个“至多”计数问题。
    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 {
    // 利用恒等式 exactly(k) = atMost(k) - atMost(k-1)，问题变成两个“至多”计数问题。
    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)$，其中 $n$ 为数组长度。atMost 被调用两次，每次调用里 right 走 $n$ 步，left 只增不减因而总共也最多走 $n$ 步，哈希表的增删查都是均摊常数。凭的是「至多 k 种」的单调性——右端扩张不会让左边界回退，所以内层 while 的总执行次数被 left 的总位移量摊平，而不是每轮各跑一遍。

空间复杂度：$O(k)$，哈希表在任意时刻最多同时装 k + 1 个键（加入新元素后、收缩之前的瞬间是峰值），与数组长度无关。若换成按值域开的定长计数数组，则是 $O(n)$，因为题目只保证 nums[i] <= nums.length。

关键点总结

「恰好」= 「至多 k」-「至多 k-1」，这是本题最值得带走的一条。凡是把「恰好等于某个阈值」的计数题卡住了，就试试拆成两个「至多」或两个「至少」的差，把双边约束降成单边约束。

滑动窗口能成立的前提是约束具有单调性：窗口缩小后仍满足约束。「至多 k 种」满足，「恰好 k 种」不满足。动手前先检查这一条，能省下大量在错误方向上的挣扎。

「以 right 结尾的合法子数组个数 = right - left + 1」是滑窗计数题的通用公式，成立的依据是「所有子区间也都合法」。求最长子数组时写 max(ans, right-left+1)，求个数时写 ans += right-left+1，两者共用同一套骨架。

用哈希表的键数而不是值的总和来度量「种类数」，所以计数归零必须删键。这一步不是清理内存，是维护度量本身的正确性。

累加答案的位置必须在窗口修复之后。循环不变量在收缩前是暂时被破坏的，任何依赖它的计算都要等修复完成。

面试视角：这题的高分回答有三段——先说清楚「恰好」为什么不能单指针滑窗（举出合法 left 是一段区间的例子），再抛出差分恒等式并解释集合包含关系，最后写出 atMost 并证明 right - left + 1 的贡献式。面试官常见追问有两个：「能不能一次遍历做完」（可以，同时维护两个左指针 left1、left2 分别对应至多 k 和至多 k-1，贡献为 left2 - left1，本质仍是这个恒等式）、「如果改成恰好 k 种且要求最长长度呢」（那就不能用差分了，得回到双指针配合额外记录）。

易错点总结

直接对「恰好 k 种」滑窗：nums = [1,2,1,2,3]、k = 2 中 right = 3 时合法的 left 是 0、1、2 三个值，而单个左指针只能停在一处，无论停在哪都只能贡献 1 个，最终统计出 4 左右而不是 7。

恒等式写反成 atMost(k) - atMost(k+1)：同一用例下 atMost(2) = 12、atMost(3) = 15，结果是 -3，负数答案。

计数减到 0 不删键：count 的键数只增不减，atMost(2) 在 right = 4 时键数永远是 3，while 条件恒真，left 一路涨到 5，nums[5] 直接数组越界崩溃。

收缩用 if 而非 while：atMost(2) 在 right = 4 需要连续弹出三个元素才把键数降到 2，只弹一次的话 left = 1 而窗口 [1,4] = [2,1,2,3] 仍是 3 种，贡献算成 4 而不是 2，atMost(2) 变成 14，最终答案 9。

累加写在收缩之前：right = 4 时用未修复的 left = 0 算出贡献 5 而不是 2，atMost(2) 变成 15（恰好等于 atMost(3)），最终答案 10。

贡献式写成 answer += 1：只统计了每个 right 对应的最长窗口本身，atMost(2) 和 atMost(1) 都变成 5，相减得 0。

收缩条件写成 count.size() >= k：窗口被压到只剩 k-1 种，atMost(2) 实际算出的是 atMost(1) = 5，再减 atMost(1) 得 0。

给 atMost 的 k = 0 情形返回 1（误以为空子数组要计入）：k = 1、nums = [1,1] 时正确答案是 3，atMost(1) = 3、atMost(0) 若返回 1 则结果变成 2，整体少 1。

两次 atMost 调用共用哈希表或 left（写成成员变量却没重置）：第二次调用带着上一次残留的计数开始，[1,2,1,2,3] 会得到毫无规律的错值，而且小样例常常侥幸通过。

用 Set 代替计数哈希表：左指针弹出 nums[left] 时无从知道该值在窗口里是否还有别的副本。atMost(2) 在 right = 4 收缩时弹出 nums[0] = 1，Set 会直接删掉 1，可窗口 [1,4] 里 nums[2] 还是 1，种类数被少算，left 提前停下，答案偏大。

相似题目

题目	难度	考察点
340. 至多包含 K 个不同字符的最长子串	中等	本题 `atMost` 子过程的原型，只是把「累加 `right-left+1`」换成「取最大窗口长度」
159. 至多包含两个不同字符的最长子串	中等	340 中 k 固定为 2 的特例，可以用两个变量代替哈希表
904. 水果成篮	中等	换皮的 159，考点是从题面里读出「至多两种」这个隐藏约束
930. 和相同的二元子数组	中等	同一个差分套路，但阈值换成「和」而非「种类数」，也可用前缀和加哈希表一次遍历
1248. 统计「优美子数组」	中等	把奇数视作 1、偶数视作 0 后即为 930，考的是问题转化
3. 无重复字符的最长子串	中等	相当于 k 等于窗口长度的极端情形，约束是「无重复」，求最长而不计数
713. 乘积小于 K 的子数组	中等	同样用 `right-left+1` 累加计数，但单调量是乘积，需要额外处理元素为 1 及溢出
1004. 最大连续1的个数 III	中等	约束是「窗口内 0 的个数至多 k」，用一个整数计数即可，不需要哈希表
76. 最小覆盖子串	困难	约束方向反过来是「至少覆盖」，窗口在满足条件时收缩求最小，收缩时机与本题相反
LCR 016. 无重复字符的最长子串	中等	与 3 同题，可直接套用