697. 数组的度

阳光穿透心脏的1/2处 2022-10-31 00:55 105阅读 0赞

##### 题目描述： #####

给定一个非空且只包含非负数的整数数组 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 范围内的整数。

##### 题解： #####

**哈希表方法**

记原数组中出现次数最多的数为 *x*，那么和原数组的度相同的最短连续子数组，必然包含了原数组中的全部 *x*，且两端恰为 *x* 第一次出现和最后一次出现的位置。

因为符合条件的 *x* 可能有多个，即多个不同的数在原数组中出现次数相同。所以为了找到这个子数组，我们需要统计每一个数出现的次数，同时还需要统计每一个数第一次出现和最后一次出现的位置。

在实际代码中，我们使用哈希表实现该功能，每一个数映射到一个长度为 *3* 的数组，数组中的三个元素分别代表这个数出现的次数、这个数在原数组中第一次出现的位置和这个数在原数组中最后一次出现的位置。当我们记录完所有信息后，我们需要遍历该哈希表，找到元素出现次数最多，且前后位置差最小的数。

**代码**

/** * @param {number[]} nums * @return {number} */
    var findShortestSubArray = function(nums) { 
        const numsMap = { }
    
        for(let [i, num] of nums.entries()) { 
            if(numsMap[num] !== undefined) { 
                numsMap[num][0] ++
                numsMap[num][2] = i
            } else { 
                numsMap[num] = [1, i, i]
            }
        }
    
        let maxCount = 0, minLen = 0
    
        for (let [count, start, end] of Object.values(numsMap)) { 
            let len = end - start + 1
            if(maxCount < count) { 
                maxCount = count
                minLen = len
            } else if (maxCount === count) { 
                if(minLen > len) { 
                    minLen = len
                }
            }
        }
    
        return minLen
    };