济南网站建设咨 询小七,网页制作基础教程第2版答案,wordpress 个人简历模板,杭州做小型app的公司给定一个非空且只包含非负数的整数数组 nums#xff0c;数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组#xff0c;返回其长度。
示例 1#xff1a;
输入#xff1a;[1, 2, 2, 3, 1] 输出…给定一个非空且只包含非负数的整数数组 nums数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组返回其长度。
示例 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.
解题思路
关键找到出现次数最多的元素可能多个相同元素的头尾元素的距离就是与 nums 拥有相同大小的度的最短连续子数组因为这个子数组保证涵盖到所有的出现次数最多的元素拥有相同大小的度。 两个hashmap分别记录每个数字出现的次数和第一次出现的位置用来维护出现频数和所能产生的子数组长度
代码
class Solution {public int findShortestSubArray(int[] nums) {int max-1,resInteger.MAX_VALUE;MapInteger,Integer mapnew HashMap();MapInteger,Integer map2new HashMap();for (int i 0; i nums.length; i) {map.put(nums[i],map.getOrDefault(nums[i],0)1);if(!map2.containsKey(nums[i])) map2.put(nums[i],i);int temp i-map2.get(nums[i])1;if(max-1||map.get(nums[i])map.get(max)||nums[i]max||(map.get(nums[i])map.get(max)tempres))
//需要替换子数组的4种情况 1.最大频数还没初始化2.出现更大频数3.目前最大频数元素的子数组长度更新4.新元素的频数跟之前的最大频数相同但是生成的子数组长度更短{restemp; maxnums[i];}}return res;}
}