Degree of an Array

Question

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.

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.

LeetCodeleetcode.com/problems/degree-of-an-array

Solution

/*
@param: int[] input numbers
@return: smallest length of subarray that has same degree
Algorithm: countMap记录频次, indexMap记录下标
1.初始化
2.if curCount >= count 取最小的length
*/
public int findShortestSubArray(int[] nums) {
    if (nums.length <= 1) {
        return nums.length;
    }
    
    Map<Integer, Integer> countMap = new HashMap<>();
    Map<Integer, Integer> indexMap = new HashMap<>();
    
    int count = 0;
    int min = 50000;
    for (int i = 0; i < nums.length; i++) {
        int temp = 1;
        if (!indexMap.containsKey(nums[i])) {
            indexMap.put(nums[i], i);
            countMap.put(nums[i], 1);
        }else {
            temp = countMap.get(nums[i])+1;
            countMap.put(nums[i], temp);
        }
        if (temp >= count) {
            if (temp > count) {
                min = 50000;
            }
            count = temp;                                
            min = Math.min(i - indexMap.get(nums[i]) + 1, min);                    
        }
        
    }
    return min;
}