哈希算法题目：数组的度

题目描述
给定一个非空且只包含非负整数的整数数组 nums，数组的度的定义是指数组中任意元素出现频率的最大值。你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，并返回其长度。

示例 1
输入：nums = [1,2,2,3,1]
输出：2
解释：

• 元素 1 出现了 2 次，元素 2 出现了 2 次，所以数组的度是 2。
• 拥有相同度的最短连续子数组有两个：
  • [2, 2] 长度为 2
  • [1, 2, 2, 3, 1] 长度为 5
    因此最短的长度是 2。

示例 2
输入：nums = [1,2,2,3,1,4,2]
输出：6
解释：

• 元素 2 出现了 3 次，是出现次数最多的元素，所以度是 3。
• 包含所有 3 个 2 的最短连续子数组是 [2,2,3,1,4,2]，长度为 6。

解题过程循序渐进讲解

步骤 1：理解题意与目标
我们需要计算数组的“度”——即任意数字出现的最大频率。然后，在数组中找出一个尽可能短的连续子数组，使得这个子数组的“度”与原数组相同。换句话说，这个子数组必须包含所有出现频率等于“度”的数字，并且包含每个这样的数字的全部出现位置（因为这些数字是构成“度”的关键）。

关键点：

• 可能有多个数字出现频率都等于最大频率（度）。
• 对每个这样的数字，我们需要在子数组中包含它的所有出现位置。
• 子数组是连续的，所以只需要考虑每个数字第一次出现和最后一次出现的位置。

步骤 2：分析如何用哈希表记录信息
我们通过遍历数组一次，记录每个数字的以下信息：

1. 出现次数（用于计算度）。
2. 第一次出现的下标。
3. 最后一次出现的下标。

这样，对于每个数字，包含它的所有出现的最短子数组长度就是 last[index] - first[index] + 1。
对于所有出现次数等于“度”的数字，我们取这个长度的最小值。

步骤 3：数据结构设计
可以用三个哈希表：

• count：键是数字，值是出现的次数。
• first：键是数字，值是该数字第一次出现的索引。
• last：键是数字，值是该数字最后一次出现的索引。

实际上，我们可以将 first 和 last 合并成一个记录，但为了清晰，分开也可以。但为了节省空间，我们可以在一次遍历中同时更新这些信息。

更优设计：
我们只需两个哈希表：

• count：记录出现次数。
• first：记录第一次出现的索引。
  而最后一次出现的索引可以在遍历过程中实时更新，因为最后一次出现就是当前遍历到的位置。

步骤 4：算法步骤

1. 初始化 count 和 first 为空的哈希表，初始化 max_freq = 0 表示当前的最大频率，min_len = 数组长度 表示最终结果。
2. 遍历数组 nums，对于每个元素 nums[i]：
   • 如果 nums[i] 不在 first 中，说明是第一次出现，记录 first[nums[i]] = i。
   • 更新 count[nums[i]] += 1。
   • 当前数字的出现次数 freq = count[nums[i]]。
   • 如果 freq > max_freq，说明发现了新的最大频率，更新 max_freq = freq，并且更新 min_len = i - first[nums[i]] + 1（因为这个数字是当前唯一的出现最多次的数字，包含它所有出现的最短长度就是这个）。
   • 如果 freq == max_freq，说明有另一个数字也出现了这么多次，比较包含当前数字的最短长度 i - first[nums[i]] + 1 与当前 min_len，取较小值更新 min_len。
3. 遍历结束后，min_len 就是答案。

步骤 5：举例说明
以 nums = [1,2,2,3,1,4,2] 为例：

初始化：count={}, first={}, max_freq=0, min_len=7

i=0, num=1: first[1]=0, count[1]=1, freq=1 > max_freq(0) -> max_freq=1, min_len=0-0+1=1
i=1, num=2: first[2]=1, count[2]=1, freq=1 == max_freq -> 比较长度 1-1+1=1 与 min_len=1，取 1
i=2, num=2: count[2]=2, freq=2 > max_freq(1) -> max_freq=2, min_len=2-1+1=2
i=3, num=3: first[3]=3, count[3]=1, freq=1 < max_freq 忽略
i=4, num=1: count[1]=2, freq=2 == max_freq -> 比较长度 4-0+1=5 与 min_len=2，取 2
i=5, num=4: first[4]=5, count[4]=1, freq=1 < max_freq 忽略
i=6, num=2: count[2]=3, freq=3 > max_freq(2) -> max_freq=3, min_len=6-1+1=6

最终 min_len=6。

步骤 6：复杂度分析

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

步骤 7：验证边缘情况

• 数组只有一个元素，如 [5]：度为 1，最短子数组就是它自己，长度 1。
• 所有元素相同，如 [7,7,7]：度为 3，最短子数组是整个数组，长度 3。
• 多个数字出现频率相同，如 [1,2,3]：度为 1，最短子数组长度是 1（任意一个元素）。

算法正确。

最终解答
实现代码（Python示例）：

def findShortestSubArray(nums):
    first, count = {}, {}
    max_freq = 0
    min_len = len(nums)
    
    for i, num in enumerate(nums):
        if num not in first:
            first[num] = i
        count[num] = count.get(num, 0) + 1
        freq = count[num]
        
        if freq > max_freq:
            max_freq = freq
            min_len = i - first[num] + 1
        elif freq == max_freq:
            min_len = min(min_len, i - first[num] + 1)
    
    return min_len

这样就解决了“数组的度”问题，核心是通过哈希表一次遍历记录每个数字的首次出现位置和频次，动态更新最大频次对应的最短子数组长度。