594 最长和谐子序列（哈希表）

古城微笑少年丶 2022-09-01 00:57 144阅读 0赞

**1. 问题描述：**

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是 1 。现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

**示例 1：**

输入：nums = \[1,3,2,2,5,2,3,7\]  
输出：5  
解释：最长的和谐子序列是 \[3,2,2,2,3\]

**示例 2：**

输入：nums = \[1,2,3,4\]  
输出：2

**示例 3：**

输入：nums = \[1,1,1,1\]  
输出：0

**提示：**

1 <= nums.length <= 2 \* 10 ^ 4  
\-10 ^ 9 <= nums\[i\] <= 10 ^ 9  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-harmonious-subsequence

**2. 思路分析：**

子序列与集合中的子集是一一对应的，所以选择一个子序列相当于是从集合中选择一个子集，所以我们可以使用一个哈希表来记录一下每一个数字出现的次数，遍历一下哈希表，找出值相差为1的集合，对于每一个相差为1的集合取一个max即可。

**3. 代码如下：**

from typing import List
    import collections
    
    
    class Solution:
        def findLHS(self, nums: List[int]) -> int:
            dic = collections.defaultdict(int)
            for x in nums:
                dic[x] += 1
            res = 0
            for k, v in dic.items():
                # 判断相差为为1的另外一类是否存在
                if k - 1 in dic:
                    res = max(res, dic[k] + dic[k - 1])
            return res