LeetCode 697. 数组的度

Question

给定一个非空且只包含非负数的整数数组 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.

示例 2：

输入：[1,2,2,3,1,4,2]
输出：6

题解

简单题重拳出击。先找出数组的度。再找出数组中对应这个度的元素。由于这个元素有第一个位置和最后一个位置，与 nums 拥有相同大小的度的最短连续子数组就是以这个元素的第一个位置和最后一个位置截取的子数组。

找数组的度可以先通过建立哈希表，记录每个出现的数的频度，再找出最大的频度。哈希表除记录频度外，还要记录某个数第一次出现的位置和最后一次出现的位置，以求出最短子数组的长度。

代码

class Solution {
  public int findShortestSubArray(int[] nums) {
    HashMap<Integer,Val> map = new HashMap<Integer,Val>(); 
    for(int i = 0;i < nums.length;i++){//遍历原数组，记录每个数的信息
      if(map.containsKey(nums[i])){
        map.get(nums[i]).lastIndex = i;
        map.get(nums[i]).num++;
      }else{
        Val val = new Val(i);
        map.put(nums[i],val);
      }
    }
    int maxDegree = Integer.MIN_VALUE;
    for(Map.Entry<Integer, Val> entry: map.entrySet()){//遍历哈希表，求出数组的度
      if(entry.getValue().num>maxDegree){
        maxDegree = entry.getValue().num;
      }
    }
    int minLen = Integer.MAX_VALUE;
    for(Map.Entry<Integer, Val> entry: map.entrySet()){//再次遍历哈希表，找到最短子数组
      if(entry.getValue().num==maxDegree){
        if(entry.getValue().lastIndex - entry.getValue().firstIndex + 1 < minLen){
          minLen = entry.getValue().lastIndex - entry.getValue().firstIndex + 1;
        }
      }
    }
    return minLen;
  }
}
//自定义一个类，用来存储某个元素的信息。
class Val{
  int firstIndex;
  int lastIndex;
  int num;
  public Val(int index){
    this.firstIndex = this.lastIndex = index;
    num = 1;
  }
}