[MonkeySolutions] Simple Java with thinking process


  • 0

    This solution is quite straightforward. Just want to share my thinking process.

    1, If the order does not matter in ether input, intermediate and required output,we suppose to use pointer, hashmap, etc. In this case, we need to store some statuses. We choose hashmap.
    2, Sometimes we may think whether this is the best space complexity. Suppose one situation. [1,2,3,4,5,6], when the pointer reach to 6, we need to know the previous status. So o(n) cannot be got rid of.
    

    Here is the code:
    '''

    public int findLHS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }
        int max = 0;
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            int key = entry.getKey();
            if (map.containsKey(key+1)) {
                max = Math.max(max, entry.getValue()+map.get(key+1));
            }
            if (map.containsKey(key-1)) {
                max = Math.max(max, entry.getValue()+map.get(key-1));
            }
        }
        return max;
    }
    

    '''


Log in to reply
 

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