力扣-594-最长和谐序列

题目：
594.Longest Harmonious Subsequence
We define a harmounious array as 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.

1
2
3
4

Example 1:
Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

题目大意：
和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度
注意：序列元素不一定是数组中连续的元素。

解题思路：
对于当前的元素x，他可以和x+1组成和谐子序列。所以可以先用一个hashMap存储每个数出现的次数，这样可以在O(1)的时间内得到x和x+1出现的次数。
首先遍历一遍数组，得到哈希映射。随后遍历哈希映射，设当前遍历到的键值对为(x,value),则要判断x+1在哈希中对应的值，不断迭代更新x和x+1出现的总和。
可以参考leetcode官网这个ppt讲解，更好理解。

注意其中getOrDefault(key,defaultValue:当Map集合中有这个key时，就使用这个key值，如果没有就使用默认值defaultValue)和map.keySet():返回key值的Set集合.

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Java:
//时间复杂度O(n),空间复杂度O(n)
public int findLHS(int[] nums){
    Map<Integer,Integer> map = new HashMap<>();
    int res = 0;
    for(int num : nums){
        map.put(num,map.getOrDefault(num,0) + 1);//Key出现次数
    }
    for(int key : map.keySet()){
        if(map.containsKey(key + 1)){
            res = Math.max(res, map.get(key) + map.get(key + 1));
        }
    }
    return res;
}