package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.com/problems/degree-of-an-array/
 */
public class Problem697 {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            } else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }
        int max = 0;
        List<Integer> list = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (max < entry.getValue()) {
                list.clear();
                list.add(entry.getKey());
                max = entry.getValue();
            } else if (max == entry.getValue()) {
                list.add(entry.getKey());
            }
        }
        int result = Integer.MAX_VALUE;
        for (int num : list) {
            int tmpResult = 0;
            int count = 0;
            boolean first = true;
            for (int i = 0; i < nums.length; i++) {
                if (count == max) {
                    break;
                }
                if (nums[i] == num) {
                    count++;
                    if (first) {
                        first = false;
                    }
                }
                if (!first) {
                    tmpResult++;
                }
            }
            result = Math.min(result, tmpResult);
        }
        return result;
    }
}

@@ -298,24 +298,133 @@
 ashMap%3C%3E();%0A
+        Map%3CInteger, Integer%3E left = new HashMap%3C%3E();%0A        Map%3CInteger, Integer%3E right = new HashMap%3C%3E();%0A
         for 
@@ -451,32 +451,32 @@
 .length; i++) %7B%0A
-
             if (
@@ -624,32 +624,293 @@
 ;%0A            %7D%0A
+            if (!left.containsKey(nums%5Bi%5D)) %7B%0A                left.put(nums%5Bi%5D, i);%0A            %7D%0A        %7D%0A        for (int i = nums.length - 1; i %3E= 0; i--) %7B%0A            if (!right.containsKey(nums%5Bi%5D)) %7B%0A                right.put(nums%5Bi%5D, i);%0A            %7D%0A
         %7D%0A      
@@ -1396,542 +1396,68 @@
     
-int tmpResult = 0;%0A            int count = 0;%0A            boolean first = true;%0A            for (int i = 0; i %3C nums.length; i++) %7B%0A                if (count == max) %7B%0A                    break;%0A                %7D%0A                if (nums%5Bi%5D == num) %7B%0A                    count++;%0A                    if (first) %7B%0A                        first = false;%0A                    %7D%0A                %7D%0A                if (!first) %7B%0A                    tmpResult++;%0A                %7D%0A            %7D%0A            result = Math.min(result, tmpResult
+result = Math.min(result, right.get(num) - left.get(num) + 1
 );%0A 

Solve problem 697