java数据结构与算法刷题-----LeetCode697. 数组的度

方法一：hash表

此方法是工作中时间可以使用的，因为它的时间和空间复杂度都相对平衡，也较低。下面介绍的方法二，工作中是坚决不可以使用的，因为会造成大量的空间浪费。

1. 先遍历一遍数组，记录每个元素的出现次数，起始下标和结尾下标
2. 然后遍历hash表，找到最大出现次数的元素，然后通过len = 结尾下标 - 起始下标 +1获取其长度
3. 如果遇到相同出现次数的元素，选择长度更小的作为答案（题目要求）

class Solution {
    public int findShortestSubArray(int[] nums) {
        //哈希表，key为nums数组中的元素值。value为int数组，共3个元素保存当前key的[度,起始下标,结尾下标]
        Map<Integer, int[]> map = new HashMap<Integer, int[]>();
        int n = nums.length;//数组长度
        for(int i = 0;i < n ; i++){
            if(map.containsKey(nums[i])){//如果当前map已经有该数字
                map.get(nums[i])[0]++;//当前数字的出现次数+1
                map.get(nums[i])[2] = i;//当前数字出现的末尾下标
            }else map.put(nums[i],new int[]{1,i,i});//第一次遇到就放入map，出现次数为1，起始下标为i，结尾下标为i
        }
        int maxNum = 0, minLen = 0;//maxNum保存拥有最大的度的元素，minLen保存，包含最大度的所有元素且尽可能短的数组长度
        for(Map.Entry<Integer, int[]> entry: map.entrySet()){
            int[] arr = entry.getValue();
            if(maxNum < arr[0]){//如果当前保存的 元素的度， 没有当前遍历元素的度大
                maxNum = arr[0];//就保留大的度，也就是当前遍历元素的这个，更大的度
                minLen = arr[2] - arr[1] +1;//更新子数组长度
            }else if(maxNum == arr[0]){//如果两个元素的度相同，
                //我们保留更短的子数组长度
                if(minLen>arr[2] - arr[1] + 1) minLen = arr[2] - arr[1] +1;
            }
        }
        return minLen;//根据题意，返回包含度最大所有元素的最短子数组长度
    }
}

方法二：数组下标线性索引

此方法的做题效率更高，对于某些题目来说，确实无论是实际应用和做题的角度来说，都是不错的方法。但不是这道题应该使用的方法。对于这道题也只能做题时可以使用一下了。因为它用数组中的值的范围，作为数组x的下标，数组x作为hash表，来进行常数级的存取。但是假设，数组中存储的元素范围是1 ~ 100000000，那么就需要申请长度为100000000的数组空间。假设有一个数组需要处理，[1,2,3,4,4,4,10000000000]，如果使用正经的hash表，只需要7个空间。而使用这种方法，空间复杂度就是10000000000。如果实际应用场景你写出这种代码，100%会被辞退的。因此，这个方法，对于这道题，只能大家做题使用，千万不要放到工作场景中。

class Solution {
    /**此方法空间复杂度过高，不推荐工作场景下使用，假设nums = [1,2,2,10000000000] 那么空间复杂度就是 10000000000，
    * 而hash表空间复杂度是4.
    */
    public int findShortestSubArray(int[] nums) {
        /** 首先，先建立一个数组，用下标来表示nums中所有元素的值。最大值-最小值 +1 就是nums的value值范围 */
        int min=Integer.MAX_VALUE;//保存数组中元素的最小值
        int max=Integer.MIN_VALUE;//保存数组中元素的最大值
        //获取最大最小值
        for(int i: nums){
            max=Math.max(max,i);
            min=Math.min(min,i);
        }
        int[] count=new int[max-min+1];//建立数组，数组下标对应nums元素的取值范围，空间复杂度会非常高
        int maxCount=0;//找到元素的最大出现次数
        //找到最大次数
        for(int i:nums){//依次遍历数组元素
            //以当前元素 - min 作为下标，让count数组对应值+1，代表这个值出现了一次
            //因为数组下标从0开始，count[0]代表nums数组的最小值，i - min就是count对应下标
            maxCount=Math.max(maxCount,++count[i-min]);//保存出现次数最大的
        }
        if(maxCount==1){//如果最大出现次数为1，直接返回1
            return 1;
        }
        /****否则需要寻找出现次数最大（也就是 == maxCount）的元素，然后获取其起始和末尾下标 */
        int res=nums.length;
        int start,end=nums.length-1;
        int num=0;
        //寻找
        for(int i=0;i<count.length;i++){
            if(count[i]!=maxCount){
                continue;
            }
            start=0;
            end=nums.length-1;
            num=min+i;
            while(start<end&&nums[start]!=num){
                start++;
            }
            while(start<end&&nums[end]!=num){
                end--;
            }
            res=Math.min(res,end-start+1);
        }
        return res;
    }
}