脚撕LeetCode(697)Easy
题目地址：https://leetcode-cn.com/problems/degree-of-an-array/submissions/
给定一个非空且只包含非负数的整数数组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 https://leetcode-cn.com/problems/degree-of-an-array/submissions/
提示：
nums.length在1到 50,000 区间范围内。
nums[i]是一个在 0 到 49,999 范围内的整数。
理解：
这道题很明显，就是找出：出现次数最多的数字，如果不止一个，就找出first和last间距最短的
一、爆破法
爆破法一开始我想到的是创建一个数组存放次数，一个数组存放first，一个数组放lasy
但是这么做有个问题，就是他的nums[i]是0-49999也就是要创建一个5w的数组，这样的话别说时间，就是空间上都拿不到成绩。
于是我想到了另一个办法，用map，一般情况下map比int的时间和空间都垃圾，但是有特殊情况，就是你明知道他不会出现很大的数字范围，但是题目明说了如果你创建数组就必须创建很大的数组，这样会造成可知的时间和空间上的浪费，所以我这里选择了用map结构
思路：
先创建一个map，key是数字，value是一个数组，数组len=3 分别存放count，first和last
循环遍历，如果key存在就增加count和修改last，如果不存在就新增一个，count=1，first=当前索引，last=当前索引
最后就是循环遍历找到count最大值，然后计算他的长度（注意长度是last-first+1而不是last-first）
运行结果如下：
89 / 89 个通过测试用例
状态：通过
执行用时: 11 ms
内存消耗: 42.9 MB
public int findShortestSubArrayMe(int[] nums) {
Map<Integer, int[]> map = new HashMap<>();
int[] ints;
for (int i = 0; i < nums.length; i++) {
if (!map.containsKey(nums[i])) {
// value的数组分别是 出现次数，first，last
map.put(nums[i], new int[]{1, i, i});
} else {
ints = map.get(nums[i]);
ints[0]++;
ints[2] = i;
}
}
int maxCount = 0;
int maxCountLen = 0;
int len;
for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
ints = entry.getValue();
len = ints[2] - ints[1] + 1;
if (maxCount < ints[0]) {
maxCount = ints[0];
maxCountLen = len;
} else if (maxCount == ints[0]) {
if (len < maxCountLen) {
maxCountLen = len;
}
}
}
return maxCountLen;
}看到官方也是这个做法，所以我在评论区里寻找大佬的做法，在评论区遇到了一个接近双百的做法觉得不错，这边贴出来
二、大佬的接近双百做法：
首先创建了一个数组，大小是5w
然后在遍历传来的数组的记录进这个数组的同时，比较出maxcount
然后再将这个数组用0全部填充。
这次再次循环找到count=max的last下标r
循环找到max的左指针l，然后用r-l+1去和res（返回值）做比较得出最小的len
执行结果如下：
89 / 89 个通过测试用例
状态：通过
执行用时: 7 ms
内存消耗: 40 MB
public int findShortestSubArray(int[] nums) {
int len = nums.length, MAXN = 50_000;
int[] map = new int[MAXN];
int max = 0;
for(int num: nums) {
max = Math.max(max, ++map[num]);
}
Arrays.fill(map, 0);
int l = 0, r = 0, res = MAXN;
while(r < len) {
if(max > ++map[nums[r++]]) continue;
while(max > map[nums[l++]]--) ;
res = Math.min(res, r - l + 1);
}
return res;
}大佬的做法虽然简洁但是总感觉哪里还能优化，（执行结果很稳定）我想尝试优化一下
执行结果如下：
89 / 89 个通过测试用例
状态：通过
执行用时: 26 ms
内存消耗: 40 MB
public int findShortestSubArrayMe2(int[] nums) {
int len = nums.length, MAXN = 50_000;
int[] map = new int[MAXN];
int max = 0;
for(int num: nums) {
max = Math.max(max, ++map[num]);
}
Arrays.fill(map, 0);
int l = 0, r = 0, res = MAXN;
int maxCountNum = 0;
while(r < len) {
if(max > ++map[nums[r++]]) continue;
maxCountNum = nums[r-1];
while(maxCountNum != nums[l++]) ;
res = Math.min(res, r - l + 1);
l = 0;
}
return res;
}但是看了一下，空间是100%了，时间却大不如大佬的做法，但我总感觉大佬的想法是还能有优化空间的。留给以后的自己吧，说不定刷题数起来了，在遇到这种问题就很快乐。
哟吼11.50了，事已至此，先吃饭吧。
腾讯云开发者
