Easy understand Java Solution (Beats 100% solutions)


  • 5
    E
     public int findShortestSubArray(int[] nums) {
            if (nums.length == 0 || nums == null) return 0;
            Map<Integer, int[]> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++){
               if (!map.containsKey(nums[i])){
                   map.put(nums[i], new int[]{1, i, i});  // the first element in array is degree, second is first index of this key, third is last index of this key
               } else {
                   int[] temp = map.get(nums[i]);
                   temp[0]++;
                   temp[2] = i;
               }
            }
            int degree = Integer.MIN_VALUE, res = Integer.MAX_VALUE;
            for (int[] value : map.values()){
                if (value[0] > degree){
                    degree = value[0];
                    res = value[2] - value[1] + 1;
                } else if (value[0] == degree){
                    res = Math.min( value[2] - value[1] + 1, res);
                } 
            }
            return res;
        }
    

  • 0
    T

    @eatcode brilliant solution


  • 0
    R

    '''int degree=0;
    for (int i = 0; i < nums.length; i++){
    if (!map.containsKey(nums[i])){
    map.put(nums[i], new int[]{1, i, i});
    } else {
    int[] temp = map.get(nums[i]);
    temp[0]++;
    temp[2] = i;
    degree=Math.max(degree,temp[0]);
    }
    }

        int min=0;
        for (int[] value : map.values()){
           if(value[0]!=degree) continue;
             else if (value[0] == degree){
               min = value[2] - value[1] + 1;
            }
        }
        return min;'''
    

    I suggest if you want to minimize your code in the enhanced for loop,is that you declare a variable "degree",and every time you increment temp[0],you compare it with degree,and at the end of for loop you will get the max degree


  • 0
    Y

    @eatcode
    My solution is similar:

    class Solution {
        public int findShortestSubArray(int[] nums) {
            int degree = 0;
            int res = Integer.MAX_VALUE;
            Map<Integer, int[]> map = new HashMap<>();
            for(int i = 0; i < nums.length; i ++) {
                if(!map.containsKey(nums[i])) {
                    map.put(nums[i], new int[]{1, i, i});
                }
                else {
                    int[] c = map.get(nums[i]);
                    c[0] ++;
                    c[2] = i;
                }
                if(map.get(nums[i])[0] > degree) degree = map.get(nums[i])[0];
            }
            for(int key : map.keySet()) {
                if(map.get(key)[0] == degree) {
                    res = Math.min(res, map.get(key)[2] - map.get(key)[1] + 1);
                }
            }
            return res;
        }
    }
    

  • 0
    J

    @yaoyimingg In the case of input [2,1], why shouldn't the output be 2 instead of 1? Since the maximum degree here is 1 and the minimum subarray that contains all the maximum degree elements is 2.


  • 0
    Y

    @john221 I think you misunderstood the question. In the case of [2,1], both elements '2' and '1' appears once so the degree of the array is 1. We need to find out a subarray that has the shortest length and the same degree of the input array.The 3 subarrays :[2,1], [1] and [2] has the same degree of [2,1], so the answer is 1 which is the length of [1] or [2].


Log in to reply
 

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