LeetCode 697. 数组的度

2024-10-12 HGNULB 约 10 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 697. 数组的度

题意分析

定义一个数组的「度」为其中任一元素的最大出现频数。给定非空整数数组 nums，要求找出一个连续子数组，使它的度与原数组相同，返回这个子数组的最短长度。

先把「度相同」这个条件翻译清楚。子数组的度不可能超过原数组的度，所以「度相同」等价于「子数组里存在某个元素，出现次数达到了原数组的最大频数」。而某个元素在子数组里的出现次数不可能超过它在原数组里的总次数，因此这个元素必须是原数组里的一个最高频元素，且它在原数组中的每一次出现都必须落在子数组内。

这就把问题化简成一个非常具体的形式：对每个最高频元素 x，能覆盖它全部出现位置的最短连续区间，就是从它第一次出现的下标到最后一次出现的下标这一段，长度为 last - first + 1；答案是所有最高频元素中这个长度的最小值。注意最高频元素可能有多个（比如 [1, 2, 2, 3, 1] 里 1 和 2 都出现两次），必须全部比较，不能取第一个。

约束透露的信号：数组长度上限 $5 \times 10^4$，元素取值范围 $[0, 5 \times 10^4]$ 但可以稀疏，说明可以用哈希表按元素分组统计，$O(n)$ 或 $O(n \log n)$ 都能过，而 $O(n^2)$ 枚举所有子数组再验证会超时。

边界：数组保证非空，长度为 1 时度为 1，答案是 1；所有元素互不相同时度为 1，任意单个元素都构成合法答案，结果也是 1——好的实现应该让这两种情况自然落入主逻辑而不需要特判。

解法：记录首次位置与次数

核心思路

暴力法是枚举所有 $O(n^2)$ 个子数组，各自统计一遍度再和原数组的度比较，整体 $O(n^3)$（或用增量统计降到 $O(n^2)$）。瓶颈在于它把「子数组」当成了自由变量去搜索，而上一节已经证明候选答案根本没有那么多——真正有资格成为答案的区间只有「最高频元素的首末位置区间」这不超过 $n$ 个。

所以正确的做法是按元素分组：对每个不同的值 x，只需要三个量——出现次数 count[x]、首次下标 first[x]、末次下标。而末次下标其实不必单独存：从左往右扫描时，当前下标 i 就是 nums[i] 到目前为止的末次出现位置，所以 i - first[nums[i]] + 1 正好是「覆盖 nums[i] 前 count[nums[i]] 次出现所需的区间长度」。这样一趟扫描即可，不需要第二遍遍历。

维护两个标量 degree 和 answer，循环不变量是：扫描完前 i + 1 个元素后，degree 是前缀 nums[0..i] 的度，answer 是这段前缀中所有达到该度的元素各自覆盖区间长度的最小值。

每读入一个 nums[i]，先更新它的 first 与 count，算出它当前的覆盖长度 length，然后分三种情况维持不变量：freq > degree 说明前缀的度被刷新了，之前所有候选全部作废，degree = freq 且 answer = length（此刻唯一达标的元素就是 nums[i]）；freq == degree 说明 nums[i] 是又一个达标元素，answer = min(answer, length)；freq < degree 说明它够不上，什么都不做。

扫描到末尾时前缀就是整个数组，不变量直接给出答案。answer 的初值取 nums.length：整个数组本身必定是一个合法解，用它当上界既安全又省掉了「首次赋值」的特判。

这个写法只用一趟扫描和两个哈希表，是面试中最推荐的手写方案；比「先扫一遍求出度，再扫一遍找最短区间」的两趟版本更紧凑，但要求想清楚「当前下标即末次位置」这一点。

解题步骤

初始化：count 记录每个值出现次数，first 记录每个值首次出现的下标，degree = 0，answer = nums.length。degree 初值取 0 才能保证第一个元素（频数 1）必然触发 freq > degree 分支，从而正确地把 answer 设为 1。

记录首次位置：first.putIfAbsent(num, i)（Go 里先判键是否存在再写）。关键是只在第一次出现时写入，用 put 覆盖会让 first 退化成「最近一次出现的位置」，算出的长度永远偏小。

更新次数：freq = count.getOrDefault(num, 0) + 1 并写回。这里取的是更新后的次数，因为它要和 degree 直接比较。

计算覆盖长度：length = i - first.get(num) + 1。i 承担了「末次出现位置」的角色，这是省掉一趟遍历的原因；+1 是闭区间长度，漏掉会让答案整体少 1。

刷新度：freq > degree 时 degree = freq 并直接赋值 answer = length，不能写成 answer = min(answer, length)——度提高了意味着旧候选全部失效，此时更小的旧 answer 反而是错的。

并列时取更短：freq == degree 时 answer = min(answer, length)，处理多个元素同为最高频的情况。

返回 answer，不需要任何后处理。

以 nums = [1, 2, 2, 3, 1, 4, 2] 走一遍（每行给出 i、num、更新后的 freq、length，以及本轮结束时的 degree / answer）。

i = 0，num = 1：首次出现记 first[1] = 0，freq = 1，length = 0 - 0 + 1 = 1。1 > 0 触发刷新，degree = 1，answer = 1。
i = 1，num = 2：记 first[2] = 1，freq = 1，length = 1 - 1 + 1 = 1。1 == 1 并列，answer = min(1, 1) = 1。
i = 2，num = 2：first[2] 已存在保持 1，freq = 2，length = 2 - 1 + 1 = 2。2 > 1 刷新，degree = 2，answer 被直接覆盖为 2——注意这里旧值 1 必须丢掉，长度为 1 的区间度只有 1，够不上新的度。
i = 3，num = 3：记 first[3] = 3，freq = 1，length = 1。1 < 2，两个分支都不进，answer 保持 2。
i = 4，num = 1：first[1] 保持 0，freq = 2，length = 4 - 0 + 1 = 5。2 == 2 并列，answer = min(2, 5) = 2。
i = 5，num = 4：freq = 1 < 2，不动，answer 仍为 2。
i = 6，num = 2：first[2] 保持 1，freq = 3，length = 6 - 1 + 1 = 6。3 > 2 刷新，degree = 3，answer = 6。

返回 6。核对一下：整个数组里 2 出现三次是唯一的最高频元素，它的首末下标是 1 和 6，覆盖区间 [1, 6] 长度正是 6。倘若第 i = 6 轮把刷新分支误写成 answer = min(answer, length)，就会保留 i = 4 时的 2，返回一个度只有 2 的区间，答案错误。

代码实现

class Solution {
    public int findShortestSubArray(int[] nums) {
        // count 记出现次数，first 记首次下标，两者合起来就能算出覆盖某个数的最短区间。
        Map<Integer, Integer> count = new HashMap<>();
        Map<Integer, Integer> first = new HashMap<>();
        int degree = 0;
        // 数组非空，整个数组一定是一个合法答案，用它当上界。
        int answer = nums.length;

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            first.putIfAbsent(num, i);
            int freq = count.getOrDefault(num, 0) + 1;
            count.put(num, freq);

            int length = i - first.get(num) + 1;
            if (freq > degree) {
                degree = freq;
                answer = length;
            } else if (freq == degree) {
                answer = Math.min(answer, length);
            }
        }

        return answer;
    }
}

func findShortestSubArray(nums []int) int {
    // count 记出现次数，first 记首次下标，两者合起来就能算出覆盖某个数的最短区间。
    count := make(map[int]int)
    first := make(map[int]int)
    degree := 0
    // 数组非空，整个数组一定是一个合法答案，用它当上界。
    answer := len(nums)

    for i, v := range nums {
        if _, ok := first[v]; !ok {
            first[v] = i
        }
        count[v]++

        length := i - first[v] + 1
        if count[v] > degree {
            degree = count[v]
            answer = length
        } else if count[v] == degree {
            if length < answer {
                answer = length
            }
        }
    }

    return answer
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是数组长度。只有一趟从左到右的扫描，循环体内是常数次哈希读写与比较，哈希操作均摊 $O(1)$。

空间复杂度：$O(k)$，其中 $k$ 是数组中不同值的个数，最坏（元素两两不同）为 $O(n)$。开销来自 count 与 first 两张哈希表，degree、answer、length 都是标量。若元素取值范围有限且连续，可以把两张哈希表换成定长数组把常数压下去，但量级不变。

关键点总结

先把「子数组的度等于原数组的度」化简成「必须完整覆盖某个最高频元素的所有出现位置」，候选区间数量就从 $O(n^2)$ 塌缩到 $O(k)$。这种「先证明最优解一定长成某个形状，再只枚举那个形状」的化简是数组类题目的通用突破口。

从左往右扫描时，当前下标天然就是当前元素的末次出现位置，因此只需记首次位置就能得到完整区间，一趟扫描顶两趟。这个技巧在所有「首末位置构成区间」的题里都能复用。

first 必须用「不存在才写」的语义（putIfAbsent），这是整段代码里语义最脆弱的一行，改成无条件 put 就全错。

「度被刷新」与「度并列」必须走不同的更新逻辑：前者要覆盖式赋值，后者才取最小值。混为一谈是本题最典型的逻辑错误，面试时主动讲清这个分界能显著加分。

answer 初值取数组长度而不是无穷大，既保证有意义的上界，也让「所有元素互不相同」这类边界自然得到正确结果 1。

最高频元素可能有多个，任何「找到最大频数就停下」的写法都会漏解。

易错点总结

刷新度时写成 answer = Math.min(answer, length)：[1, 2, 2, 3, 1, 4, 2] 会返回 2 而非 6，返回的区间度只有 2，根本不满足题意。这是本题第一大错误。

first 用 put 而不是 putIfAbsent：first 变成「上一次出现位置」，[1, 2, 2, 3, 1] 中 1 的首次位置被覆盖成 4，算出长度 1，返回 1，而正确答案是 2。

长度公式漏掉 + 1：[1, 1] 算出 1 - 0 = 1，返回 1，但覆盖两个 1 至少需要长度 2。所有答案都会偏小 1。

degree 初值设成 1：[5] 这种单元素输入进不了 freq > degree 分支，只走并列分支 answer = min(1, 1) 侥幸正确；但若把 answer 初值也改成极大值，就会返回 Integer.MAX_VALUE。两个初值必须配套。

比较时用更新前的次数：先比较 count.get(num) 再自增，[1, 1] 第二次遇到 1 时拿到的 freq 仍是 1，度永远停在 1，返回 1。

count.get(num) 直接用于新键：Java 里对未出现过的值调用 get 返回 null，拆箱时抛 NullPointerException，任何输入的第一个元素就会崩。必须用 getOrDefault。

只记录首末位置，最后再扫哈希表求答案时忘记比较频数：[1, 2, 2, 3, 1, 4, 2] 里 1 的区间是 [0, 4] 长度 5、2 的区间是 [1, 6] 长度 6，若不筛掉频数不足的元素直接取最小，会返回 3 的区间长度 1。

误以为答案区间必须以最高频元素开头和结尾之外还需扩展：多写了「向两侧扩到边界」的逻辑，[1, 2, 2, 1] 会返回 4 而不是正确的 2，度相同即可，不需要包含其他元素。

用排序或 TreeMap 求最大频数：把 $O(n)$ 拖成 $O(n \log n)$ 且完全没有必要；更糟的是排序破坏了下标信息，首末位置就再也算不出来了。

枚举所有子数组逐一统计度：n 取到 $5 \times 10^4$ 时 $O(n^2)$ 已是 $2.5 \times 10^9$ 次操作，必然超时。

相似题目

题目	难度	考察点
594. 最长和谐子序列	简单	同样按值哈希计数，但求的是相邻两值频数之和且对象是子序列，无需下标信息
347. 前 K 个高频元素	中等	只要频数排名不要位置，重点在计数后如何用堆或桶排序选出前 K 个
387. 字符串中的第一个唯一字符	简单	计数加下标的最简形式，两趟扫描分别统计与查找频数为 1 的最左位置
219. 存在重复元素 II	简单	同样维护值到下标的映射，但只需记最近一次出现位置来判断间距是否不超过 k
560. 和为 K 的子数组	中等	换成前缀和作哈希键来定位子数组，考察的是和而非频数
209. 长度最小的子数组	中等	同为「最短满足条件子数组」，但条件具备单调性，可用滑动窗口而非分组统计
3. 无重复字符的最长子串	中等	用哈希记录字符上次出现位置来收缩左边界，求的是最长而非最短
128. 最长连续序列	中等	也是用哈希把 $O(n \log n)$ 排序降到 $O(n)$，但统计的是数值的连续性