一、题目粗心
https://leetcode.cn/problems/…
给定一个非空且只蕴含非正数的整数数组 nums，数组的 度 的定义是指数组里任一元素呈现频数的最大值。
你的工作是在 nums 中找到与 nums 领有雷同大小的度的最短间断子数组，返回其长度。
示例 1：
输出：nums = [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：
输出：nums = [1,2,2,3,1,4,2]
输入：6
解释：
数组的度是 3，因为元素 2 反复呈现 3 次。
所以 [2,2,3,1,4,2] 是最短子数组，因而返回 6。
提醒：
- nums.length 在 1 到 50,000 范畴内。
- nums[i] 是一个在 0 到 49,999 范畴内的整数。
二、解题思路
首先给数组的度下一个定义，给一个数组，某个或某些数字呈现最多的次数为该数组的度。题目要求咱们找到最短的子数组使其和原数组领有雷同的度。
思路：统计每个数字呈现的次数，用哈希来建设数字与呈现次数的映射，咱们要求与该数组有雷同度的最小长度子数组，咱们要晓得每个数字的度，与其首次呈现的地位，这样咱们要定义两个哈希一个来存呈现的次数，一个来存首次呈现的地位。咱们再定义一个变量 degree 来示意数组的度。遍历数组以后遍历地位能够看作是最初一次呈现的地位即尾地位，累加以后数字呈现的次数，如果数字是第一次呈现，建设数字与首地位的映射，如果以后数字的呈现次数等于 degree 时，以后地位为尾地位，用 endIndex – startIndex + 1 来更新后果；如果以后数字的呈现次数大于 degree，阐明之前的后果代表的数字不是呈现最多的，间接将后果更新为 endIndex – startIndex + 1，而后 degree 也更新为以后数字呈现的次数。
三、解题办法
3.1 Java 实现
public class Solution {public int findShortestSubArray(int[] nums) {Map<Integer, Integer> countMap = new HashMap<>();
Map<Integer, Integer> firstIdxMap = new HashMap<>();
int ans = nums.length;
int degree = 0;
for (int i = 0; i < nums.length; i++) {int num = nums[i];
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
// 记录首地位
if (countMap.get(num) == 1) {firstIdxMap.put(num, i);
}
if (countMap.get(num) == degree) {ans = Math.min(ans, i - firstIdxMap.get(num) + 1);
} else if (countMap.get(num) > degree) {ans = i - firstIdxMap.get(num) + 1;
degree = countMap.get(num);
}
}
return ans;
}
}四、总结小记
- 2208/8/23 这两天天气不错