Given a non-empty array of non-negative integersnums, 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 ofnums, that has the same degree asnums.

Example 1:

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，然后用two pointer找最短的序列。

这样写运行时间很长，只击败了不到1%的用户。。。

class Solution {
    public int findShortestSubArray(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;

        int[] count = new int[50000];
        int degree = 0;
        for(int i = 0; i < nums.length; i++) {
            count[nums[i]]++;
            degree = Math.max(degree, count[nums[i]]);
        }

        count = new int[50000];
        int res = nums.length;
        int i = 0;
        int j = 0;
        int d = 0;

        while(i < nums.length) {
            while(i < nums.length && d < degree) {
                count[nums[i]]++;
                d = Math.max(d, count[nums[i]]);
                i++;
            }
            res = Math.min(res, i - j);

            while(j <= i && d == degree) {
                count[nums[j]]--;

                d = 0;
                for(int k = 0; k < count.length; k++)
                    d = Math.max(d, count[k]);
                j++;
            }

            res = Math.min(res, i - j + 1);
        }

        return res;
    }
}

另一种思路：找到整个array的degree，找到所有出现次数等于degree的值，在找到这些值第一次和最后一次出现的index

class Solution {
    public int findShortestSubArray(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;

        int[] count = new int[50000];
        int d = 0;
        for(int i = 0; i < nums.length; i++) {
            count[nums[i]]++;
            d = Math.max(d, count[nums[i]]);
        }

        List<Integer> candidates = new ArrayList<Integer>();
        for(int i = 0; i < count.length; i++) {
            if(count[i] == d)
                candidates.add(i);
        }

        int res = nums.length;
        for(int i = 0; i < candidates.size(); i++) {
            int len = getLen(nums, candidates.get(i));
            res = Math.min(res, len);
        }

        return res;
    }

    public int getLen(int[] nums, int n) {
        int left = 0;
        while(left < nums.length && nums[left] != n)
            left++;

        int right = nums.length - 1;
        while(right >= 0 && nums[right] != n)
            right--;

        return right - left + 1;
    }
}