594. Longest Harmonious Subsequence

Version #2 HashMap
Time O(n)
Space O(n)
第一次傻逼了，update max的时候还是iterate nums
然后很慢
发现其实iterate keyset 就可以了
快很多

93.71 %
class Solution {
    public int findLHS(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        // key->nums, value->count
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, 1 + map.getOrDefault(num, 0));
        }
        int max = 0;
        for (int num : map.keySet()) {
            if (map.containsKey(num - 1)) {
                max = Math.max(max, map.get(num) + map.get(num - 1));
            }
        }
        return max;
    }
}

Version #1 Naiive two pointers
[left, right] ensures diff between this subarray is <= 1
Time O(nlogn)
Space O(1)
97.43 %
class Solution {
    public int findLHS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int result = 0;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            while (nums[left] < nums[right] - 1) {
                left++;
            }
            if (nums[left] + 1 == nums[right]) {
                result = Math.max(right - left + 1, result);
            }
        }
        return result;
    }
}