697. 数组的度

1. 题目简介

难度：简单，原题链接：697. 数组的度。

给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

2. 问题分析

数组的度是某个数字出现次数的最大值。要让连续子数组具有相同的度，就必须完整保留至少一个达到最高次数的数字。

假设数字 t 出现了最多次，那么包含全部 t 的最短连续子数组，一定从它第一次出现的位置开始，到最后一次出现的位置结束。再向外延伸没有必要，向内缩短则会少包含一个 t。因此，这个候选区间的长度为 lastIndex(t) - firstIndex(t) + 1。

如果多个数字都达到最高次数，就要比较各自的候选区间。例如 [1, 2, 2, 3, 1] 的度为 2：数字 1 对应的区间长度是 5，数字 2 对应的区间长度是 2，所以答案为 2。

代码用 degrees 为每个数字保存一个 int[3]，依次记录出现次数、首次下标和末次下标。扫描数组时更新这三项，并维护最高次数 maxDegree；扫描结束后，只比较次数等于 maxDegree 的记录，取区间长度的最小值。

3. 代码实现

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, int[]> degrees = new HashMap<>();
        int maxDegree = 0;
        for (int i = 0; i < nums.length; i++) {
            int[] cur = degrees.getOrDefault(nums[i], new int[3]);
            cur[0]++;
            if (cur[0] == 1) {
                cur[1] = i;
            }
            cur[2] = i;
            degrees.put(nums[i], cur);
            maxDegree = Math.max(maxDegree, cur[0]);
        }

        int res = nums.length;
        for (int[] value : degrees.values()) {
            if (value[0] == maxDegree) {
                res = Math.min(res, value[2] - value[1] + 1);
            }
        }
        return res;
    }
}

4. 复杂度分析

• 时间复杂度：O(n)，按哈希表操作的平均成本计算，扫描数组后再遍历各数字的统计记录。
• 空间复杂度：O(n)，每个不同的数字对应一份 int[3] 记录，最多有 n 份。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明