【C++刷题】力扣-#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 。

题解

为了找到数组中与数组度相同大小的最短连续子数组，我们可以使用以下步骤：

计算每个元素的频率：使用哈希表（或字典）来计算数组中每个元素的出现次数。
确定度：找到频率的最大值，这就是数组的度。
找到每个元素的索引：对于每个元素，记录它在数组中出现的所有索引。
计算最短子数组长度：对于每个频率等于度的元素，计算包含该元素所有出现次数的最短子数组的长度。这可以通过找到该元素最后出现和第一次出现的索引，然后计算这两个索引之间的差值加一来实现。
返回最短长度：在所有频率等于度的元素中，找到最短的子数组长度，并返回这个长度。

代码实现

int findShortestSubArray(vector<int>& nums) {unordered_map<int, int> count; // 记录每个数字出现的次数unordered_map<int, vector<int>> positions; // 记录每个数字出现的位置int degree = 0;int n = nums.size();// 计算每个元素的出现次数和位置for (int i = 0; i < n; ++i) {int num = nums[i];count[num]++;positions[num].push_back(i);if (count[num] > degree) {degree = count[num];}}int shortestLength = n;// 对于每个频率等于度的元素，计算最短子数组的长度for (auto& pair : count) {if (pair.second == degree) {int length = positions[pair.first].back() -positions[pair.first].front() + 1;shortestLength = min(shortestLength, length);}}return shortestLength;
}