# 0697. Degree of an Array
###### tags: `Leetcode` `Easy`
Link: https://leetcode.com/problems/degree-of-an-array/

## 思路 $O(N)$ $O(N)$
用三个hashmap分别记录每个元素出现的第一个和最后一个位置，以及出现的次数

one pass解法 是需要记录每个元素出现的次数和第一次出现的位置
注意语法```first.putIfAbsent()```
## Code

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer,Integer> left = new HashMap<>(), right = new HashMap<>(), count = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            if(!left.containsKey(nums[i])) left.put(nums[i],i);
            right.put(nums[i],i);
            count.put(nums[i],count.getOrDefault(nums[i],0)+1);
        }
        int degree = Collections.max(count.values());
        int res = Integer.MAX_VALUE;
        for(int i = 0;i < nums.length;i++){
            if(count.get(nums[i])==degree){
                res = Math.min(res, right.get(nums[i])-left.get(nums[i])+1);
            }
        }
        return res;
    }
}

One Pass 解法

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        Map<Integer, Integer> first = new HashMap<>();
        int degree = 0;
        int ans = -1;
        for(int i = 0;i < nums.length;i++){
            count.put(nums[i], count.getOrDefault(nums[i], 0)+1);
            first.putIfAbsent(nums[i], i);
            if(count.get(nums[i])>degree){
                ans = i-first.get(nums[i])+1;
                degree = count.get(nums[i]);
            }
            else if(count.get(nums[i])==degree){
                ans = Math.min(ans, i-first.get(nums[i])+1);
            }
        }
        return ans;
    }
}