697. 数组的度

一、题目描述

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

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

二、解题思路

需要计算数字的度，只能遍历一次数组来计算，可以用数组来保存次数，但是为了简单起见，还是直接用集合类吧。

得到数字的度数后，还需要知道最大度数，这个也顺便在计算数字的度数时一起更新了。

知道哪些数字有最大度数后，就剩下计算它们的最短子数组长度了：

• 这个子数组，实际上就是这个数字第一次和最后一次出现之间的子数组

所以还必须知道每个数字第一次和最后一次出现的位置，len = lastPos - firstPos + 1。

我一开始的思路是，得到最大度数和数字后，再逐个寻找这些数字的第一次和最后一次的位置，但是看了官方解答后，没想到可以在前面统计度数时，顺便吧前后出现的位置记录下来，有点意思啊~

三、复杂度分析

• 时间 O(n)
• 空间 O(1)

四、参考代码

/**
 * 找到与nums拥有相同大小的度的最短连续子数组，返回其长度
 *
 * @param nums 数组
 * @return 长度
 */
private int findShortestSubArray(int[] nums) {
    // 计算每个数的度数，以及最大度数
    int maxCount = 0;
    Map<Integer, int[]> countMap = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int[] count = countMap.get(nums[i]);
        if (count == null) {
            count = new int[3];
            count[1] = i;
        }
        count[0]++;
        count[2] = i;
        countMap.put(nums[i], count);
        if (count[0] > maxCount) {
            maxCount = count[0];
        }
    }

    // 计算最大度数数字的最短数组长度
    int minLen = nums.length;
    for (Map.Entry<Integer, int[]> entry : countMap.entrySet()) {
        int[] count = entry.getValue();
        if (count[0] == maxCount) {
            int len = count[2] - count[1] + 1;
            if (len < minLen) {
                minLen = len;
            }
        }
    }

    return minLen;
}