数组的度

题目描述：
给定一个非空且只包含非负整数的数组 nums，数组的“度”被定义为数组中出现次数最多的元素的出现次数。你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
示例：
输入：nums = [1,2,2,3,1]
输出：2
解释：
数组的度是 2，因为元素 1 和 2 的出现次数均为 2。
包含 2 的最短连续子数组是 [2,2]，长度为 2；包含 1 的最短连续子数组是 [1,2,2,3,1]，长度为 5。所以答案是 2。

解题过程：

1. 理解目标

我们需要找到数组中出现频率最高的元素（可能多个），并针对每个这样的元素，计算其第一次出现和最后一次出现之间的子数组长度，然后取这些长度中的最小值。

2. 核心思路

• 用哈希表记录每个数字的出现次数、首次出现位置、最后出现位置。
• 遍历数组，更新哈希表信息。
• 遍历哈希表，找到出现次数最多的数字，并计算对应子数组长度（最后位置 - 首次位置 + 1）。
• 如果出现次数相同，取最短子数组长度。

3. 步骤详解

步骤 1：初始化数据结构

• 使用三个哈希表，或一个哈希表存储复合信息。这里用一个哈希表，键是数字，值是一个三元组 (出现次数, 首次索引, 最后索引)。
• 也可以用三个独立的哈希表：countMap、firstMap、lastMap，更直观。

步骤 2：第一次遍历数组
遍历 nums，索引为 i，当前数字为 num：

• 如果 num 不在 firstMap 中，说明是第一次出现，记录 firstMap[num] = i。
• 每次出现都更新 lastMap[num] = i，并增加 countMap[num] 的计数。

步骤 3：确定最大度

• 遍历 countMap，找到最大计数值，这就是数组的度 maxDegree。

步骤 4：计算最短子数组

• 再次遍历 countMap，对于每个计数等于 maxDegree 的数字 num，计算子数组长度：lastMap[num] - firstMap[num] + 1。
• 取这些长度中的最小值。

4. 示例推演

以 nums = [1,2,2,3,1] 为例：

初始化：

countMap = {}
firstMap = {}
lastMap = {}

遍历：

• i=0, num=1: firstMap[1]=0, lastMap[1]=0, countMap[1]=1
• i=1, num=2: firstMap[2]=1, lastMap[2]=1, countMap[2]=1
• i=2, num=2: lastMap[2]=2, countMap[2]=2
• i=3, num=3: firstMap[3]=3, lastMap[3]=3, countMap[3]=1
• i=4, num=1: lastMap[1]=4, countMap[1]=2

结果：

countMap: {1:2, 2:2, 3:1}
firstMap: {1:0, 2:1, 3:3}
lastMap: {1:4, 2:2, 3:3}

最大度 maxDegree = 2（数字1和2）。

计算长度：

• 数字1: last[1]-first[1]+1 = 4-0+1 = 5
• 数字2: last[2]-first[2]+1 = 2-1+1 = 2
  最短长度为 2。

5. 优化

可以一次遍历完成：用一个哈希表存储 (计数, 首次索引, 最后索引)，遍历时更新，并同时追踪当前最大度和最短长度。

伪代码：

countMap = {}  # 数字 -> [计数, 首次索引, 最后索引]
maxDegree = 0
minLength = 无穷大

for i from 0 to n-1:
    num = nums[i]
    if num not in countMap:
        countMap[num] = [1, i, i]
    else:
        countMap[num][0] += 1
        countMap[num][2] = i
    # 更新最大度和最短长度
    [cnt, first, last] = countMap[num]
    if cnt > maxDegree:
        maxDegree = cnt
        minLength = last - first + 1
    else if cnt == maxDegree:
        minLength = min(minLength, last - first + 1)

return minLength

6. 复杂度分析

• 时间复杂度：O(n)，一次遍历。
• 空间复杂度：O(n)，哈希表存储每个不同数字的信息。

7. 关键点

• 理解“度”的定义和“最短连续子数组”的含义。
• 利用哈希表高效记录每个数字的统计信息和位置。
• 注意可能有多个数字的出现次数都等于最大度，需比较它们对应的子数组长度。

这样，我们就找到了与原始数组具有相同度的最短连续子数组的长度。