findShortestSubArray.py

# -*- encoding: utf-8 -*-
'''
@project :   LeetCode
@File    :   findShortestSubArray.py
@Contact :   9824373@qq.com
@Desc    :
            给定一个非空且只包含非负数的整数数组 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

@Modify Time      @Author    @Version    @Desciption
------------      -------    --------    -----------
2020-02-29   zhan      1.0         None
'''

from  typing import List

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        record = {}
        max_len = 0
        for i, char in enumerate(nums):
            if char not in record:
                record[char] = {'left': i, 'right': i, 'count': 1}
                max_len = max(1, max_len)
            else:
                record[char]['right'] = i
                record[char]['count'] += 1
                max_len = max(record[char]['count'], max_len)

        min_len = len(nums)
        for k, v in record.items():
            if v['count'] == max_len:
                min_len = min(v['right'] - v['left'] + 1, min_len)

        return min_len


if __name__ == '__main__':
    a = [1, 2, 2, 3, 1]

    ans = Solution().findShortestSubArray(a)
    print(ans)