class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
}
};
697. 数组的度
给定一个非空且只包含非负数的整数数组 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 范围内的整数。相似题目
原站题解
golang 解法, 执行用时: 32 ms, 内存消耗: 6.8 MB, 提交时间: 2021-06-02 14:39:25
type entry struct {
cnt, l, r int
}
func findShortestSubArray(nums []int) int {
mp := map[int]entry{}
for i, num := range nums {
if e, has := mp[num]; has {
e.cnt++
e.r = i
mp[num] = e
} else {
mp[num] = entry{1, i, i}
}
}
maxCnt, ans := 0, 0
for _, m := range mp {
if m.cnt > maxCnt {
maxCnt = m.cnt
ans = m.r - m.l + 1
} else if m.cnt == maxCnt {
ans = min(ans, m.r-m.l+1)
}
}
return ans
}
func min(a, b int) int {
if a > b {
return b
}
return a
}