原题地址（简单）

方法1—哈希表

思路

感觉这题其实可以来个中等难度的。。。
思路就是找出数组的度，然后找出出现次数等于度的那些数，然后再找出这些数的始末位置，看看哪个长度最小，就酱……

代码

开始只想到了用unordered_map存储数和其出现次数，代码写的较为麻烦些。

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, int> um;
        for(auto num : nums)    um[num]++;
        vector<int> v;
        int n = nums.size(), ans = n, freq = 0;
        for(auto it = um.begin(); it!= um.end(); it++) {   // 找出度
            if(it->second > freq)   freq = it->second;
        }
        for(auto it = um.begin(); it!= um.end(); it++) {   //找出出现次数为度的那些数
            if(it->second == freq)  v.push_back(it->first);
        }
        for(int i=0; i<v.size(); i++) {   // 寻找这些数的始末位置
            int l = 0, r = n - 1;
            while(l < n) {
                if(nums[l] != v[i])
                    l++;
                else    break;
            }
            while(r >= 0) {
                if(nums[r] != v[i])
                    r--;
                else    break;
            }
            ans = min(ans, r - l + 1);
        }
        return ans;
    }
};

后来看了题解，发现如果用unordered_map同时存储数的出现次数以及始末位置，会更快.

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, vector<int>> um;
        int n = nums.size(), ans = n, freq = 0;
        for(int i = 0; i < n; i++) {
            if(um.count(nums[i])) {
                um[nums[i]][0]++;
                um[nums[i]][2] = i;
            }
            else {
                um[nums[i]] = {1, i, i};
            }
        }

        for(auto it = um.begin(); it!= um.end(); it++) {
            if(it->second[0] > freq) {
                freq = it->second[0];
                ans = it->second[2] - it->second[1] + 1;
            }
            else if(it->second[0] == freq)
                ans = min(ans, it->second[2] - it->second[1] + 1);
        }

        return ans;
    }
};

时空复杂度

均为O(N)