本文主要是介绍LeetCode第四天（697. 数组的度），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
刚开始题目都不太能读懂，写不出来，然后去B站寻找了一下教学视频（up主讲的是真的很细致！！！）这是分开一步步写的，官解是步骤跨越显得有点难（因为我是菜狗）
class Solution {public int findShortestSubArray(int[] nums) {//思路：遍历数组nums，将每个元素出现的次数存在HashMap中，得到数组的度//最短连续子数组要和nums数组度的大小相同，就要包含出现次数最多的元素的首位置、末位置//如果有多个出现次数最大的元素，就比较末位置-首位置最小的数组长度（遍历HashMap）//key存储元素，value存储元素出现次数、首位、末位Map<Integer,int[]> map = new HashMap<>();//定义数组的度int maxCount = 0;//定义数组长度int len = nums.length;//遍历数组，找出度，首位，末位for(int i = 0;i < len;i++){int num = nums[i];if(map.containsKey(num)){//元素不是第一次出现int[] data = map.get(num);//更新次数data[0] = data[0] + 1;//更新末位data[2] = i; //更新数组的度maxCount = Math.max(maxCount,data[0]);}else{//元素是第一次出现int[] data = new int[3];data[0] = 1;data[1] = i;data[2] = i;map.put(num,data);//更新数组的度maxCount = Math.max(maxCount,data[0]);}}//定义首位末位差值int diff = len;//得到map里面的int[]数组Set<Integer> KeySet = map.keySet();//遍历HashMapfor(Integer num : KeySet){int[] data = map.get(num);//如果该元素的出现次数=数组的度，计算首末位置的差值，把最小的数组长度赋值给diffif(data[0] == maxCount){diff = Math.min(diff,data[2]-data[1]+1);}}return diff;}
}官解：
方法一：哈希表
思路及解法记原数组中出现次数最多的数为 xxx，那么和原数组的度相同的最短连续子数组，必然包含了原数组中的全部 xxx，且两端恰为 xxx 第一次出现和最后一次出现的位置。
因为符合条件的 xxx 可能有多个，即多个不同的数在原数组中出现次数相同。所以为了找到这个子数组，我们需要统计每一个数出现的次数，同时还需要统计每一个数第一次出现和最后一次出现的位置。
在实际代码中，我们使用哈希表实现该功能，每一个数映射到一个长度为 333 的数组，数组中的三个元素分别代表这个数出现的次数、这个数在原数组中第一次出现的位置和这个数在原数组中最后一次出现的位置。当我们记录完所有信息后，我们需要遍历该哈希表，找到元素出现次数最多，且前后位置差最小的数。
class Solution {public int findShortestSubArray(int[] nums) {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.get(nums[i])[0]++;map.get(nums[i])[2] = i;} else {map.put(nums[i], new int[]{1, i, i});}}int maxNum = 0, minLen = 0;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;}
}
这篇关于LeetCode第四天（697. 数组的度）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
