数组的度（LeetCode 697）——LogicStack-LeetCode 哈希表计数解法深度解析-平芜编程栈

教程
文档

【免费下载链接】LogicStack-LeetCode

公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码

项目地址：https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode

本篇指南以 LogicStack-LeetCode 仓库中的《697. 数组的度（简单）》题解为骨架，围绕「数组的度」这一核心概念，系统讲解如何用「静态数组计数」与「哈希表计数」两种思路在 O(n) 时间内求出最短连续子数组的长度，并结合仓库源码解析哈希表 = 哈希函数 + 数组的本质与选型依据。读完你将掌握：频率统计、首末位置记录、最小值聚合三类操作如何组合成一道经典简单题的完整解题套路，以及「值域确定时优先用数组计数」的实战判断准则。

一、题目回顾：什么是「数组的度」

题目描述：给定一个非空且只包含非负数的整数数组nums，数组的度（degree）的定义是指数组里任一元素出现频数的最大值。任务是在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

示例 2 中元素2出现 3 次，是整个数组的最高频，度 = 3；它首次出现在下标 1、最后出现在下标 6，因此能同时包含全部2的最短连续子数组为[2,2,3,1,4,2]，长度为6 - 1 + 1 = 6。

数据范围提示：

nums.length在1到50000区间范围内；
nums[i]是一个在0到49999范围内的整数。

Tag：哈希表。这一数据范围直接决定了下方「数组计数」解法成立的根基：值域确定且有界（本题为50000），可以用定长数组代替哈希表完成频率统计。

二、核心思路：三个要素一次扫描解决

「度」只关心出现频数，而「最短连续子数组」要求把某个值出现的全部位置都圈进来。两者结合可以得到一个非常朴素但有效的观察：

对于频数等于最大频数max的任意元素t，其「首次出现下标」到「最后出现下标」之间的连续子数组，恰好是包含t全部出现位置、且与nums拥有相同度的最短候选子数组。因此答案就是所有满足cnt[t] == max的元素中last[t] - first[t] + 1的最小值。

整体算法分为三步：

统计频数：扫描数组，用计数器记录每个值出现的次数，同时维护当前最大频数max；
记录首末位置：在扫描过程中，记录每个值「首次出现」的下标（first）与「最后出现」的下标（last）——首次出现只在第一次遇到时写入，最后出现则每次遇到都更新；
聚合答案：再次遍历数组，对所有频数等于max的值计算last - first + 1，取最小值返回。

整个过程只需要对数组做常数次扫描，时间复杂度为 O(n)，空间复杂度为 O(n)（取决于值域）。

三、解法一：静态数组计数（推荐）

由于题目明确给出值的范围是[0, 49999]，我们可以直接开三个定长数组来完成计数与首末位置记录，完全不需要哈希表。

class Solution { int N = 50010; public int findShortestSubArray(int[] nums) { int n = nums.length, max = 0, ans = 0x3f3f3f3f; int[] cnt = new int[N]; int[] first = new int[N], last = new int[N]; Arrays.fill(first, -1); for (int i = 0; i < n; i++) { int t = nums[i]; max = Math.max(max, ++cnt[t]); if (first[t] == -1) first[t] = i; last[t] = i; } for (int t : nums) { if (cnt[t] == max) ans = Math.min(ans, last[t] - first[t] + 1); } return ans; } }

class Solution { public: int N = 50010; int findShortestSubArray(vector<int>& nums) { int n = nums.size(), maxv = 0, ans = 0x3f3f3f3f; vector<int> cnt(N, 0); vector<int> first(N, -1), last(N, -1); for (int i = 0; i < n; i++) { int t = nums[i]; maxv = max(maxv, ++cnt[t]); if (first[t] == -1) first[t] = i; last[t] = i; } for (auto& t : nums) { if (cnt[t] == maxv) ans = min(ans, last[t] - first[t] + 1); } return ans; } };

class Solution: def __init__(self): self.N = 50010 def findShortestSubArray(self, nums): n, maxv, ans = len(nums), 0, 0x3f3f3f3f cnt = [0] * self.N first, last = [-1] * self.N, [-1] * self.N for i, t in enumerate(nums): cnt[t] += 1 maxv = max(maxv, cnt[t]) if first[t] == -1: first[t] = i last[t] = i for t in nums: if cnt[t] == maxv: ans = min(ans, last[t] - first[t] + 1) return ans

关键实现细节

N = 50010的取值：值域最大为49999，为了容纳下标49999并留出余量，取50010是安全且常见的做法；
first数组初始化为-1：因为合法下标从0开始，用-1作为「尚未出现」的哨兵值，避免与真实的0下标混淆；
++cnt[t]与max同步更新：每遇到一个t就自增计数并更新全局最大频数，保证第一遍扫描结束后max就是数组的度；
last[t] = i每次覆盖：保证最后留下的永远是「最后出现」的下标；
ans初始化为0x3f3f3f3f：这是算法竞赛中常用的「正无穷」写法，配合Math.min聚合即可；由于数组非空且至少有一个元素，ans最终必然被更新为合法答案。

复杂度

时间复杂度：对数组进行常数次扫描。复杂度为 O(n)；
空间复杂度：O(n)（实际为 O(valueRange)，即 O(50000)，可视为常数级别的 O(n) 上界）。

四、解法二：哈希表计数（通用）

当值的范围未知、不连续或很大（例如字符串、对象、负数、稀疏大整数）时，静态数组不再适用，此时改用哈希表完成同样的三要素统计。

class Solution { public int findShortestSubArray(int[] nums) { int n = nums.length, max = 0, ans = 0x3f3f3f3f; Map<Integer, Integer> cnt = new HashMap<>(); Map<Integer, Integer> first = new HashMap<>(), last = new HashMap<>(); for (int i = 0; i < n; i++) { int t = nums[i]; cnt.put(t, cnt.getOrDefault(t, 0) + 1); max = Math.max(max, cnt.get(t)); if (!first.containsKey(t)) first.put(t, i); last.put(t, i); } for (int t : nums) { if (cnt.get(t) == max) ans = Math.min(ans, last.get(t) - first.get(t) + 1); } return ans; } }

class Solution { public: int findShortestSubArray(vector<int>& nums) { int n = nums.size(), maxv = 0, ans = 0x3f3f3f3f; unordered_map<int, int> cnt; unordered_map<int, int> first, last; for (int i = 0; i < n; ++i) { int num = nums[i]; cnt[num] += 1; maxv = max(maxv, cnt[num]); if (first.find(num) == first.end()) first[num] = i; last[num] = i; } for (auto& t : nums) { if (cnt[t] == maxv) ans = min(ans, last[t] - first[t] + 1); } return ans; } };

class Solution: def findShortestSubArray(self, nums: List[int]) -> int: n, maxv, ans = len(nums), 0, 0x3f3f3f3f count = {} first, last = {}, {} for i, num in enumerate(nums): count[num] = count.get(num, 0) + 1 maxv = max(maxv, count[num]) if num not in first: first[num] = i last[num] = i for t in nums: if count[t] == maxv: ans = min(ans, last[t] - first[t] + 1) return ans

与解法一的差异仅在于「容器」：cnt.getOrDefault(t, 0) + 1对应数组的++cnt[t]；if (!first.containsKey(t))对应first[t] == -1的哨兵判断。算法骨架完全一致。

复杂度

时间复杂度：对数组进行常数次扫描。复杂度为 O(n)；
空间复杂度：O(n)。

五、从源码看本质：为什么数组计数更快

本题的「总结」部分点明了两种解法性能差异的根本原因：

我们知道哈希表 = 哈希函数 + 数组。由于哈希函数计算需要消耗时间（Java 中首先涉及自动装箱/拆箱，之后还要取对象的 hashCode 进行右移异或，最后才计算哈希桶的下标），以及处理哈希冲突的开销，其效率必然比不上使用静态数组进行计数。

具体到 Java 实现，解法二的每次cnt.put(t, ...)/cnt.get(t)背后至少包含三部分额外开销：

自动装箱（boxing）：基本类型int需要被包装成Integer对象才能作为泛型Map<Integer, Integer>的键；
哈希计算：调用Integer.hashCode()（返回对象自身值），再经过散列扰动与桶下标计算；
哈希冲突处理：桶内链表（极端情况下为红黑树）的遍历与比较。

而解法一的cnt[t]是纯粹的一次数组寻址，first[t]、last[t]同理，常数因子远小于哈希表的完整调用链。当数据量达到50000级别、且需要反复读写计数器时，这个常数差异在实测中会体现为可感知的耗时差距。

六、选型准则：什么时候用数组，什么时候用哈希表

原文档给出的建议可以提炼为一条通用决策规则：

对于那些数值范围确定且不太大的计算场景，使用数组进行计数，而不是使用哈希表。

具体阈值参考：

值域在 10^6 以内都可以使用静态数组计数；
本题数量级在 10^4，属于数组计数的绝对舒适区；
若值域超出可接受范围、值不连续、或键本身不是整数（字符串、元组等），则应退回哈希表方案。

这条准则在 LogicStack-LeetCode 仓库的其他题解中同样有大量印证，例如：

1. 错误的集合（简单）：同样利用值域确定的特点，用数组完成去重与计数；
1. 最长和谐子序列（简单）：在哈希表与滑动窗口之间做选择，展示了两种容器的适用边界。

完整的哈希表题型索引可参见 Index/哈希表.md，其中收录了包括本题在内的 100 余道哈希表相关题解，供横向对比学习。

七、变体与思考延伸

在掌握基本解法后，可以进一步思考以下延伸点：

度存在多个并列最大值：当多个元素频数同为max时，答案取各自last - first + 1的最小值——这正是代码中ans = Math.min(ans, ...)聚合逻辑的意义，示例 1 的1与2并列度为 2，最终取[2, 2]的长度 2 而非[1, 2, 2, 3, 1]的长度 5；
单趟合并优化：第一遍扫描已经能获得全部信息，第二遍遍历只是为了避免记录「哪些值频数为 max」的额外存储；如果希望进一步压缩，可在第一遍结束后遍历值域或使用first数组辅助判断；
无重复元素退化情形：若每个元素都只出现一次，度为 1，任何长度为 1 的子数组都是合法答案，此时任意last - first + 1 = 1，代码自然返回 1；
由「度」到「众数」的关联：本题的频数统计思想与求众数、求最高频元素等问题一脉相承，可迁移到 1838. 最高频元素的频数（中等）等进阶题目中加深理解。