数组的度（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(vectorint nums) { int n nums.size(), maxv 0, ans 0x3f3f3f3f; vectorint cnt(N, 0); vectorint 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; MapInteger, Integer cnt new HashMap(); MapInteger, 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(vectorint nums) { int n nums.size(), maxv 0, ans 0x3f3f3f3f; unordered_mapint, int cnt; unordered_mapint, 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对象才能作为泛型MapInteger, Integer的键哈希计算调用Integer.hashCode()返回对象自身值再经过散列扰动与桶下标计算哈希冲突处理桶内链表极端情况下为红黑树的遍历与比较。而解法一的cnt[t]是纯粹的一次数组寻址first[t]、last[t]同理常数因子远小于哈希表的完整调用链。当数据量达到50000级别、且需要反复读写计数器时这个常数差异在实测中会体现为可感知的耗时差距。六、选型准则什么时候用数组什么时候用哈希表原文档给出的建议可以提炼为一条通用决策规则对于那些数值范围确定且不太大的计算场景使用数组进行计数而不是使用哈希表。具体阈值参考值域在 10^6 以内都可以使用静态数组计数本题数量级在 10^4属于数组计数的绝对舒适区若值域超出可接受范围、值不连续、或键本身不是整数字符串、元组等则应退回哈希表方案。这条准则在 LogicStack-LeetCode 仓库的其他题解中同样有大量印证例如错误的集合简单同样利用值域确定的特点用数组完成去重与计数最长和谐子序列简单在哈希表与滑动窗口之间做选择展示了两种容器的适用边界。完整的哈希表题型索引可参见 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. 最高频元素的频数中等 等进阶题目中加深理解。八、小结核心结论数组的度 最大出现频数最短同度子数组 所有最大频数元素中last - first 1的最小值算法骨架一次扫描统计cnt/first/last并维护max二次扫描聚合答案时间复杂度 O(n)两种实现值域确定用静态数组本题推荐值域未知或键非整数用哈希表选型经验值域在 10^6 以内的整数计数场景优先考虑数组性能优于哈希表避免装箱、哈希计算与冲突处理开销。本题完整题解源码位于 LeetCode/691-700/697. 数组的度简单.md可结合 Index/哈希表.md 中的同类题目进行系统性训练。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐有效的数独LeetCode 36哈希表、数组与位运算三种解法全解析 — LogicStack-LeetCode 刷题指南有效的数独LeetCode 36哈希表、数组与位运算三种解法全解析 — LogicStack LeetCode 刷题指南 导读 本文是「LogicStac教程文档LeetCode 2013. 检测正方形哈希表套哈希表实现轴对齐正方形计数LogicStack-LeetCode 题解LeetCode 2013. 检测正方形哈希表套哈希表实现轴对齐正方形计数LogicStack LeetCode 题解 本文以 LogicStack Le教程文档LeetCode 1748 唯一元素的和排序双指针与计数哈希表双解法详解LogicStack-LeetCodeLeetCode 1748 唯一元素的和排序双指针与计数哈希表双解法详解LogicStack LeetCode 本文是「刷穿 LeetCode」系列中 1教程文档上一篇解锁音乐自由ncmdumpGUI深度解析与NCM格式转换实战下一篇Sunshine游戏串流终极指南从零开始打造高品质远程游戏体验创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考