Longest Harmonious Subsequence

https://leetcode.com/problems/longest-harmonious-subsequence/description/

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possiblesubsequences.

Thoughts

找两个数值相连的数，它们出现的频次最高。我们把频次统计下，然后对每个数找与它数值相邻的频次相加看是否是最大。

Code

class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
        }

        int max = 0;
        for (Integer num : freq.keySet()) {
            if (freq.containsKey(num + 1)) {
                max = Math.max(max, freq.get(num) + freq.get(num + 1));
            }
        }

        return max;
    }
}

Analysis

不需要check num-1是否在nums里，因为如果在里面在检测num-1时会检测到num.

时间复杂度O(n), 空间O(n)