数组的度(java实现)

力扣 697. 数组的度

题目说明

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

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

nums.length 在1到 50,000 区间范围内。
nums[i] 是一个在 0 到 49,999 范围内的整数。

示例

例1

输入：[1, 2, 2, 3, 1]
输出：2
解释：
输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.

例2

输入：[1,2,2,3,1,4,2]
输出：6
解释：
输入数组的度是3，元素2的出现频数最大，为3.
最短连续子数组[2,2,3,1,4,2]的长度为6，所以返回6.

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题运用哈希表再合适不过了，用哈希表来计算各元素出现的次数，存储各元素出现的首次及末次的位置，让我们来看看具体如何实现的吧。

实现

public int findShortestSubArray(int[] nums) {
        if(nums.length==1){ return 1;}
        if(nums.length==2){
            //数组长度为1，2时的特殊情况

            if(nums[0]==nums[1]){ return 2;}
            else{ return 1;}
        }
        HashMap <Integer,Integer>hashMap = new <Integer,Integer>HashMap();
        //存储数组中各数出现的次数

        HashMap <Integer,Integer>front = new <Integer,Integer>HashMap();
        //标记各数第一次出现的下标

        HashMap <Integer,Integer>rear = new <Integer,Integer>HashMap();
        //标记各数最后一次出现的下标
        
        int result = Integer.MAX_VALUE;
        //赋值为int最大值，方便比较赋值

        for (int i = 0; i < nums.length; i++) {
            hashMap.put(nums[i],hashMap.getOrDefault(nums[i],0)+1);
            //累计出现次数

            if(front.get(nums[i])==null){ front.put(nums[i],i);}
            //第一次出现，标记下标

            rear.put(nums[i],i);
            //出现一次，标记一次
        }
        int maxTimes = 0;
        for(Integer key : hashMap.keySet()){
            maxTimes = Math.max(maxTimes,hashMap.get(key));
            //计算出最大出现次数，即题中的度
        }
        for(Integer key : hashMap.keySet()){
            if(hashMap.get(key)==maxTimes){
                result = Math.min(result,rear.get(key)-front.get(key)+1);
                //如果当前元素出现次数为最大出现次数，就计算一次当前数出现的起点和终点
            }
        }
        return result;
    }