697 数组的度（哈希表）

墨蓝 2022-09-03 10:27 118阅读 0赞

**1. 问题描述：**

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

**示例 1：**

输入：\[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：**

输入：\[1,2,2,3,1,4,2\]  
输出：6

**提示：**

nums.length 在1到 50,000 区间范围内。  
nums\[i\] 是一个在 0 到 49,999 范围内的整数。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/degree-of-an-array

**2. 思路分析：**

分析题目可以知道我们可以使用**哈希表**来记录nums中数字出现的次数，并且在遍历的时候使用一个变量d来记录数字出现的最大次数，根据出现的最大次数我们重新遍历一次nums数组就可以知道哪些数字的出现次数为d，因为我们需要求解最短的能够覆盖当前出现次数最多的数字的长度，所以我们可以声明两个额外的哈希表来记录nums中的数字出现的最早位置与最晚位置，在遍历nums的时候维护每一个数字出现的最早位置与最晚位置，这样我们重新遍历原数组的时候可以判断当前的数是不是众数，如果是那么求解当前数字最晚出现的位置与最早出现位置对应区间的度就是d（区间能够覆盖当前的众数所以子数组的度为d），对于每一个满足这样条件的区间取一个min即可。

**3. 代码如下：**

from typing import List
    import collections
    
    
    class Solution:
        def findShortestSubArray(self, nums: List[int]) -> int:
            # count字典记录nums中数字的出现次数
            count = collections.defaultdict(int)
            # maxp, minp用来记录nums中每个数字出现的最开始的位置与最晚的位置
            maxp, minp = dict(), dict()
            d = 0
            for i in range(len(nums)):
                x = nums[i]
                count[x] += 1
                d = max(d, count[x])
                if x not in minp:
                    minp[x] = i
                # 每一次更新x的位置这样x最后出现的位置会将之前的位置全部覆盖掉
                maxp[x] = i
            res = 10 ** 10
            for x in nums:
                # 当前出现的数字是众数
                if count[x] == d:
                    res = min(res, maxp[x] - minp[x] + 1)
            return res