Java solution beats 90% with one HashMap and one List


  • 0

    I make an array as the value of HashMap, arr[0] represents degree, arr[1] represents the first index of the key and arr[2] represents the last index. Also, I use a list to record the nums with max degree.

        public int findShortestSubArray(int[] nums) {
            if (nums.length == 0) return 0;
            HashMap<Integer, int[]> map = new HashMap<>();
            List<Integer> list = new ArrayList<>();
            int max = 0;
            for (int i = 0; i < nums.length; i++) {
                int put = 0;
                if (map.containsKey(nums[i])) {
                    int[] arr = map.get(nums[i]);
                    put = ++arr[0];
                    arr[2] = i;
                } else {
                    int[] arr = {1, i, i};
                    put = 1;
                    map.put(nums[i], arr);
                }
                if (put > max) {
                    list.clear();
                    list.add(nums[i]);
                    max = put;
                } else if (put == max) {
                    list.add(nums[i]);
                }
            }
            int min = 50000;
            for (int i = 0; i < list.size(); i++) {
                int[] arr = map.get(list.get(i));
                min = Math.min(min, arr[2] - arr[1] + 1);
            }
            return min;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.