JZX轻语：简

LeetCode 594 - 最长和谐子序列

发表于2024年05月02日

#数组 #排序 #哈希表

使用哈希表记录每个数组的个数，然后再遍历哈希表的键key，如果key + 1也在哈希表里，则使用其和更新结果(取两者最大值)；此外，也可以先排序，然后再遍历计数，维护最近两个数字的计数，如果这两个数字相邻，则使用其和更新结果。

基于哈希表：

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        cnt = {}
        for num in nums:
            cnt[num] = cnt.get(num, 0) + 1

        return max(
            cnt[num] + cnt[num + 1] if num + 1 in cnt else 0
            for num in cnt.keys()
        )

基于排序：

from collections import deque


class Solution:
    def findLHS(self, nums: List[int]) -> int:
        nums.sort()
        q = deque(maxlen=2)
        ans = 0
        for num in nums:
            if len(q) == 0 or q[-1][0] != num:
                if len(q) == 2 and q[0][0] == q[1][0] - 1:
                    ans = max(ans, q[0][1] + q[1][1])
                q.append([num, 1])
            else:
                q[-1][1] += 1
        if len(q) == 2 and q[0][0] == q[1][0] - 1:
            ans = max(ans, q[0][1] + q[1][1])
        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/longest-harmonious-subsequence/