思路
刚开始看到题目的时候有点懵🤣
示例1解释如下:
[1,2,2,3,1] 度为2,1出现的频率为2,2出现的频率也是为2,但是1的最左和最右之间的长度为5,而2的区间长度为2,所以输出为2
示例2解释如下:
[1,2,2,3,1,4,2] 由于2出现的频率为3,那么2的最左与最右之间的区间为[2,2,3,1,4,2],长度为6,所以最终输出为6
由于需要对数组元素中各个元素进行出现次数的计数,那么可以通过哈希map来存储对应元素出现的次数,此处借助 map.meger api map.merge接口再计数的时候能够进行获取当前元素出现频率的最大值。
在知道了度值的情况下,需要再次遍历进行处理,此处借助滑动窗口的技巧。
代码
public class LC697 {
public int findShortestSubArray(int[] nums){
int len = nums.length, degree= 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i:nums){
degree = Math.max(degree,map.merge(i,1,Integer::sum));
}
map.clear();
int left = 0, right = 0, curDegree = 0, res = len;
while(right<len){
curDegree = Math.max(curDegree,map.merge(nums[right++], 1, Integer::sum));
if(curDegree == degree){
while(map.merge(nums[left], -1, Integer::sum) != degree -1){
left++;
}
curDegree = degree-1;
res = Math.min(res, right-left);
}
}
return res;
}