697. 数组的度

题目

697. 数组的度

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

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

• nums.length 在1到 50,000 区间范围内。

• nums[i] 是一个在 0 到 49,999 范围内的整数。

思路

1. 先找到数组的度

2. 再找到决定数组度的字符

3. 计算出决定数组度字符的首尾长度

题解

// 697. 数组的度

/**
 * @param {number[]} nums
 * @return {number}
 */
var findShortestSubArray = function(nums) {
    // key: 数组字符, value: 出现次数
    let map = new Map()
    nums.forEach(n => {
        map.has(n) ? map.set(n, map.get(n) + 1) : map.set(n, 1)
    })
    // 找到数组的度, 可能有多个匹配项
    // [{ 数组字符, 出现次数 }]
    let maxArr = []
    map.forEach(((value, key) => {
        if (maxArr.length === 0) {
            maxArr.push({ key, value })
        } else {
            // 如果当前出现次数大于 maxArr 中出现次数, 则更新 maxArr
            if (value > maxArr[0].value) {
                // 清空数组
                maxArr.length = 0
                maxArr.push({ key, value })
            }
            // 相等就是相同度, 则 push
            if (value === maxArr[0].value) {
                maxArr.push({ key, value })
            }
        }
    }))
    // 找到数组度的元素的长度
    let minLength = []
    maxArr.forEach(m => {
        // 首次出现 index
        let firstIndex = nums.findIndex(n => n === m.key)
        // 最后一次出现 index
        let lastIndex
        for (let i = firstIndex; i < nums.length; i++) {
            if (nums[i] === m.key) {
                lastIndex = i
            }
        }
        // 做差, 获取与原数组度相等的最小长度数组
        minLength.push(lastIndex - firstIndex + 1)
    })
    // 多个度中的最小值
    return Math.min(...minLength)
};

// test
let arr = [1, 2, 2, 3, 1]
console.log(findShortestSubArray(arr))

优化点