leetCode_697. Degree of an Array

题目描述：

Given a non-empty array of non-negative integers nums, 
the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, 
that has the same degree as nums.
Input: [1, 2, 2, 3, 1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

简单翻译下题意，给定一个非负非空整型数组，它的degree(度)指的是它中的任意一个出现频率最高的元素。
我们要做的就是找到一个这个数组的连续子数组，并计算它的长度，其中子数组和这个数组degree一样并且包含元素最少。

解法：使用两个map，一个记录元素出现的个数，一个记录这个元素第一次出现的位置，然后遍历数组，找到度数最大的元素，如果这个元素唯一，那么最后一次找到它的位置减去第一次出现的位置即为子数组的长度，如果这个元素不唯一，那么通过更新长度，来找到最短长度的那个子数组。
话不多数，代码写出来(C++)：

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        int degree = 0;// 数组的度
        int len = nums.size();
        int count = 0; // 记录长度
        map<int,int> map,firstIndex;
        for(int i = 0;i < len;i ++) {
            if(firstIndex.count(nums[i]) == 0) firstIndex[nums[i]] = i;
            map[nums[i]]++;
            if(map[nums[i]]>degree){
                degree = map[nums[i]];
                count = i - firstIndex[nums[i]] + 1;
            }
            if(map[nums[i]] == degree){
                degree = map[nums[i]];
                count = min(i - firstIndex[nums[i]] + 1,count);
            }
        }
        
        
        return count;
    }
};