> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/hash/tong-ji-pin-lv/longest-harmonious-subsequence.md).

# 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 **exactly**1.
>
> Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible[subsequences](https://en.wikipedia.org/wiki/Subsequence).

## 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)