力扣 697. 数组的度
给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
方案一：通过无序映射合并重复的数字，同时记录其出现次数，起止位置。
type node struct {
cnt int // 出现的次数
start int // 第一次出现的下标
end int // 最后一次出现的下标
}
func findShortestSubArray(nums []int) (ans int) {
// 遍历数组，计算每个元素出现的次数、第一次出现的位置和最后一次出现的位置
mp := make(map[int]*node, len(nums))
for i, num := range nums {
if node, ok := mp[num]; ok {
node.cnt++
node.end = i
continue
}
mp[num] = &node{
cnt: 1,
start: i,
end: i, // 为了防止数字只出现一次，所以结尾位置也是当前
}
}
// 找到数组的度
degree := 0
for _, v := range mp {
if v.cnt > degree {
degree = v.cnt
}
}
// 因为是求最小值，所以定义一个题目范围的最大结果
ans = 50000
// 再次遍历，找到最短连续子数组
for _, v := range mp {
if v.cnt == degree {
if sub := v.end - v.start + 1; sub < ans {
ans = sub
}
}
}
return
}
- 时间复杂度：O(n)，虽然有多个 for 循环，单它们都是顺序执行的，且每个 for 的时间复杂度都为 O(n)，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)， 因为需要一个容量为 n 的无序映射辅助计算，所以空间复杂度为 O(n)。