Easy

题目描述

给定一个由非负整数组成的非空数组 nums，数组的度定义为任何一个元素在数组中出现频次的最大值。

你的任务是在 nums 中找到与 nums 拥有相同度数的最短连续子数组，返回其长度。

示例 1：

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

输入：nums = [1,2,2,3,1,4,2]
输出：6
解释：
度数是 3，因为元素 2 重复了 3 次。
所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6。

约束条件：

  • nums.length 的范围是 1 到 50,000。
  • nums[i] 是范围在 0 到 49,999 的整数。

解题思路

解题思路

这道题需要找到与原数组拥有相同度数的最短连续子数组。关键洞察是：与原数组拥有相同度数的子数组，必须包含所有出现次数等于度数的元素的完整出现。

核心思路：

  1. 首先统计每个元素的出现次数，找到数组的度（最大出现次数）
  2. 找出所有出现次数等于度数的元素
  3. 对于每个这样的元素，计算包含它所有出现位置的最短子数组长度
  4. 返回所有这些长度中的最小值

算法步骤：

  1. 用哈希表记录每个数字的出现次数、第一次出现位置、最后一次出现位置
  2. 遍历一次数组，同时更新这些信息并找到度数
  3. 再次遍历哈希表，对于出现次数等于度数的元素，计算其子数组长度（最后位置-第一位置+1）
  4. 返回最小的子数组长度

这种方法只需要遍历数组一次，时间复杂度为O(n)，空间复杂度为O(n)。

代码实现

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, int> count, first, last;
        
        for (int i = 0; i < nums.size(); i++) {
            int num = nums[i];
            count[num]++;
            if (first.find(num) == first.end()) {
                first[num] = i;
            }
            last[num] = i;
        }
        
        int degree = 0;
        for (auto& p : count) {
            degree = max(degree, p.second);
        }
        
        int minLength = nums.size();
        for (auto& p : count) {
            if (p.second == degree) {
                minLength = min(minLength, last[p.first] - first[p.first] + 1);
            }
        }
        
        return minLength;
    }
};

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        count = {}
        first = {}
        last = {}
        
        for i, num in enumerate(nums):
            count[num] = count.get(num, 0) + 1
            if num not in first:
                first[num] = i
            last[num] = i
        
        degree = max(count.values())
        
        min_length = len(nums)
        for num, cnt in count.items():
            if cnt == degree:
                min_length = min(min_length, last[num] - first[num] + 1)
        
        return min_length

public class Solution {
    public int FindShortestSubArray(int[] nums) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        Dictionary<int, int> first = new Dictionary<int, int>();
        Dictionary<int, int> last = new Dictionary<int, int>();
        
        for (int i = 0; i < nums.Length; i++) {
            int num = nums[i];
            count[num] = count.GetValueOrDefault(num, 0) + 1;
            if (!first.ContainsKey(num)) {
                first[num] = i;
            }
            last[num] = i;
        }
        
        int degree = count.Values.Max();
        
        int minLength = nums.Length;
        foreach (var kvp in count) {
            if (kvp.Value == degree) {
                minLength = Math.Min(minLength, last[kvp.Key] - first[kvp.Key] + 1);
            }
        }
        
        return minLength;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findShortestSubArray = function(nums) {
    const count = new Map();
    const firstIndex = new Map();
    const lastIndex = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        count.set(num, (count.get(num) || 0) + 1);
        if (!firstIndex.has(num)) {
            firstIndex.set(num, i);
        }
        lastIndex.set(num, i);
    }
    
    const degree = Math.max(...count.values());
    let minLength = nums.length;
    
    for (const [num, freq] of count) {
        if (freq === degree) {
            const length = lastIndex.get(num) - firstIndex.get(num) + 1;
            minLength = Math.min(minLength, length);
        }
    }
    
    return minLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
总体复杂度O(n)O(n)

说明：

  • 时间复杂度： O(n)，需要遍历数组一次来统计信息，然后遍历哈希表来找最小长度
  • 空间复杂度： O(n)，最坏情况下所有元素都不相同，需要存储n个元素的信息

相关题目