一 🏠 题目描述
697. 数组的度
给定一个非空且只包含非负数的整数数组 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 范围内的整数。
二 🏠破题思路
2.1 🚀 关键信息
解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎
① 数组的 度 定义是指数组里任一元素出现频数的最大值 = 记录每个元素个数即可 🌹🌹🌹
② 找到与 nums 拥有相同大小度的最短连续子数组，返回其长度 = 最大个数元素的最后索引位置减去第一次索引位置加一 🌸🌸🌸
提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃
2.2 🚀 思路整理
哈希表法
每一个数映射到一个长度为 3 的数组，数组的三个元素分别代表这个数出现的次数、原数组中第一次出现的位置和在原数组中最后出现的位置。记录完所有信息后，遍历该哈希表，找到元素出现次数最多，且前后位置差最小的数 🌺🌺🌺
整理完解题思路后，直接进入第三阶段，代码实现 😃😃😃
三 🏠 代码详解
3.1 🚀 代码实现
按照我们刚才的破题思路，直接代码走起来 👇👇👇👇
int findShortestSubArray(vector<int>& nums) { unordered_map<int, vector<int>> mp; //定义哈希表 int n = nums.size(); //获取数组长度 for (int i =0; i < n; i++) { //遍历数组 if (mp.count(nums[i])) { //如果 nums[i] 存在于哈希表 mp[nums[i]][0]++; //将这个数出现次数加一 mp[nums[i]][2] = i; //将这个数最后出现位置更新 } else { mp[nums[i]] = {1, i, i}; //如果 nums[i] 不存在于哈希表, 则插入 } } int maxNum =0, minLen =0; //定义最大频数和最短长度 for (auto& [_, vec] : mp) { //遍历哈希表 if (maxNum < vec[0]) { //若频数大于当前最大频数 maxNum = vec[0]; //将最大频数更新 minLen = vec[2] - vec[1] +1; //将最短长度更新 } elseif (maxNum == vec[0]) { //频数等于当前最大频数 if (minLen > vec[2] - vec[1] +1) { //比较长度 minLen = vec[2] - vec[1] +1; //将最短长度更新 } } } return minLen; //返回最短长度 }
3.2 🚀 细节解析
看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃
那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇
unordered_map<int, vector<int>> mp; //定义哈希表
解题没什么问题，但实际应用中哈希表和 Vector 嵌套会很影响性能（STL 容器的频繁创建和销毁十分耗时）
很直白的题，无特殊点，核心是 最大个数元素的最后索引位置减去第一次索引位置加一 🐳🐳🐳
四 🏠 心路历程
为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈
博主在第一阶段提取 🚀 关键信息没有问题，在第二阶段 🚀 思路整理没有问题
代码实现使用了两个哈希表，其键均为 KEY : nums[i] 😶😶😶 ，代码如下 👇👇👇👇
int findShortestSubArray(vector<int>& nums) { std::unordered_map<int, std::pair<int, int>> map1; //VAL : beginIndex, endIndex std::unordered_map<int, int> map2; //VAL : count int len = nums.size(); //获取数组长度 for (int i =0; i < len; ++i) { //遍历数组 if (map1.find(nums[i]) == map1.end()) { map1[nums[i]] = std::make_pair(i, i); map2[nums[i]] =1; } else { map1[nums[i]].second = i; ++map2[nums[i]]; } } int maxCount =0, shortestLen = INT_MAX; for (auto& elem : map2) { if (elem.second < maxCount) continue; elseif (elem.second > maxCount) shortestLen = map1[elem.first].second - map1[elem.first].first +1; else shortestLen = std::min(map1[elem.first].second - map1[elem.first].first +1, shortestLen); maxCount = elem.second; } return shortestLen; }
