题目

难度：★☆☆☆☆
类型：数组

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。

示例

输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].
说明: 输入的数组长度最大不超过20,000.

解答

这道题有一个好处是不需要考虑数组中元素的先后顺序，大大简化了分析流程，我们可以把数组当成一个集合处理。

统计数组中每个元素出现的次数，并存放在字典当中，对于字典中每一条记录，查看某一元素num+1后是否出现在字典中，如果也出现在字典中，则num与num+1可以组成和谐数组，计算所有和谐数组长度的最大值即可。

这里我们使用python中的Counter函数进行元素的快速统计。

class Solution:
    def findLHS(self, nums):
        num_count, res = Counter(nums), 0                           # 统计列表中各个元素出现次数，并初始化结果为零
        for num, count in num_count.items():                        # 考察字典中每一条数字-次数对
            if num+1 in num_count.keys():                           # 如果数字+1也在字典中
                res = max(num_count[num]+num_count[num+1], res)     # 组成和谐数组并统计当前最大长度
        return res

如有疑问或建议，欢迎评论区留言~