leetcode 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 范围内的整数。

思路

暴力解法

假设数组中最大的度对应的数为 x ，则与 nums 拥有相同大小的度的最短连续子数组必包含原数组中的所有 x 。这里要注意，x 可能有很多个，所以要求出每一个 x 对应的最短连续子数组的长度，然后选择长度最小的一个。下面暴力解法的时间复杂度是比较高的，应该接近 $O(n^2)$ 。但是因为题目中的数的范围比较小，所以用于计数的数组也比较小，所以空间复杂度应该比哈希表低一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        int count[50006] = {0}, n = nums.size(), maximun = 0, num = 0,
            start = 0, end = 0, shumax = 0, result = 5000000;
        for (int i = 0; i < n; i++) {
            count[nums[i]]++;
            maximun = max(count[nums[i]], maximun);
        }
        for (int j = 0; j < n; j++) {
            if (count[nums[j]] == maximun) {
                start = 0, end = 0;
                for (int i = 0; i < n; i++) {
                    if (nums[i] == nums[j]) {
                        start = i;
                        break;
                    }
                }
                for (int i = n - 1; i >= 0; i--) {
                    if (nums[i] == nums[j]) {
                        end = i;
                        break;
                    }
                }
                result = min(result, end - start + 1);
            }
        }
        return result;
    }
};

哈希表

用一个哈希表，记录每个数对应的出现次数，起始位置和终止位置。当重新遇到这个数时，出现次数+1，起始位置不变，终止位置改成当前下标。最后遍历整个哈希表，比较最大的度对应的最短子数组的长度。

  1. 哈希表创建
    1
    unordered_map<int, vector<int>> mp;
  2. 哈希表查找
    1
    mp.count(number)
  3. 哈希表插入
    1
    mp[number] = {1, 2, 3};
  4. 哈希表修改
    1
    mp[index][0] = 1;
  5. 哈希表遍历
    1
    for (const auto& [num, vec] : mp)

完整的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, vector<int>> mp;
        int n = nums.size(), maximun = 0, result = 0;
        for (int i = 0; i < n; i++) {
            if (mp.count(nums[i])) {
                mp[nums[i]][0]++;
                mp[nums[i]][2] = i;
            } else {
                mp[nums[i]] = {1, i, i};
            }
        }
        for (const auto& [num, vec] : mp) {
            int tempresult = vec[2] - vec[1] + 1;
            if (vec[0] > maximun) {
                maximun = vec[0];
                result = tempresult;
            } else if (vec[0] == maximun) {
                if (tempresult < result) {
                    result = tempresult;
                }
            }
        }
        return result;
    }
};
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。