Python Solution, use Hash, O(n) time, O(n) space


  • 0
    G
    class Solution:
        def findShortestSubArray(self, nums):
            hash = dict()
            max_count = 0
            min_len = 65536
            for i in range(len(nums)):
                if nums[i] in hash:
                    hash[nums[i]]['end'] = i
                    hash[nums[i]]['count'] += 1
                    if hash[nums[i]]['count'] > max_count:
                        max_count = hash[nums[i]]['count']
                        min_len = hash[nums[i]]['end'] - hash[nums[i]]['start'] + 1
                    if hash[nums[i]]['count'] == max_count:
                        if hash[nums[i]]['end'] - hash[nums[i]]['start'] + 1 < min_len:
                            min_len = hash[nums[i]]['end'] - hash[nums[i]]['start'] + 1
                else:
                    hash[nums[i]] = {'start': i, 'end': i, 'count': 1}
    
            if 65536 == min_len:
                if 0 != len(nums):
                    return hash[nums[0]]['count']
                else:
                    return 0
            else:
                return min_len
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.