LeetCode 697. Degree of an Array

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, int[3]> m; // num => [freq, left, right]
        int n = nums.size(), degree = 1, ans = INT_MAX;
        for (int i = 0; i < nums.size(); ++i) {
            int num = nums[i];
            if (m.find(num) == m.end()) {
                m[num][0] = 1;
                m[num][1] = i;
                m[num][2] = i;
            } else {
                int freq = ++m[num][0];
                m[num][2] = i;
                degree = max(degree, freq);
            }
        }
        for (auto [_, info] : m)
            if (degree == info[0])
                ans = min(ans, info[2] - info[1] + 1);
        return ans;
    }
};