How can I solve the Degree of an Array problem?

To solve the Degree of an Array problem, track element frequencies and their first and last occurrences, then compute the minimal subarray length.

What is the optimal time complexity for this problem?

The optimal time complexity for this problem is O(N), where N is the length of the array, by scanning it just once and using a hash table.

What are the common mistakes in solving Degree of an Array?

Common mistakes include failing to track both the first and last occurrence of elements and attempting a brute force solution instead of using a hash table.

How do I handle large input arrays for this problem?

For large input arrays, the solution should remain O(N) in time and O(N) in space by using efficient array scanning and hash table usage.

What pattern does the Degree of an Array problem follow?

The problem follows the pattern of array scanning plus hash table lookup, where you efficiently track and compute frequencies and positions to determine the degree and subarray length.

#697

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

数组的度

给定一个非空且只包含非负数的整数数组 nums ，数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。示例 1：输入： nums = [1,2,2,3,1] 输出： 2 解释：输入数组的度是 2 ，因…

数组哈希表

题目描述

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

lightbulb

解题思路

方法一：哈希表

遍历数组，用哈希表记录数组每个元素出现的次数，以及首次、末次出现的位置。然后遍历哈希表，获取元素出现次数最多（可能有多个）且首末位置差最小的数。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        degree = cnt.most_common()[0][1]
        left, right = {}, {}
        for i, v in enumerate(nums):
            if v not in left:
                left[v] = i
            right[v] = i
        ans = inf
        for v in nums:
            if cnt[v] == degree:
                t = right[v] - left[v] + 1
                if ans > t:
                    ans = t
        return ans

speed

复杂度分析

指标	值
时间	O(N)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
The candidate should be comfortable with array scanning and hash table usage.
question_mark
Look for clarity in their explanation of tracking both frequency and positions.
question_mark
The ability to optimize with a single pass through the array is crucial.

warning

常见陷阱

外企场景

error
Failing to track both the first and last occurrence of elements, leading to incorrect subarray length calculations.
error
Overcomplicating the problem by attempting to brute force the subarrays instead of leveraging the hash table for direct access.
error
Not maintaining the degree accurately across elements, which could lead to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling arrays with no repeated elements, where the degree is 1.
arrow_right_alt
Considering very large arrays, where space and time efficiency becomes critical.
arrow_right_alt
Adapting the solution for arrays with negative integers, ensuring the algorithm is generalized.

help

常见问题

外企场景

继续练习

#692 前K个高频单词 #691 贴纸拼词 #690 员工的重要性