594.最长和谐子序列

https://leetcode-cn.com/problems/longest-harmonious-subsequence/

哈希

用一个哈希表map,键为num,值为数组,存储num后面与num差值在1以内的数,则这个数组里的元素就是以num开头的最长和谐子序列。一次遍历nums,求map中数组的最长长度即可

但还要注意两点:一是这样收录的map[num]中包含num-1、num和num+1,可能不构成和谐子序列。因此考虑用两个哈希表map1和map2,分别存储[num-1, num][num, num+1]范围的数字

二是当数字范围没有波动,也不是和谐子序列,只有一种情况就是map[num]数组全为num(因为若全是num+1不会收录进map[num]),因此还要用求和看是否等于len*num判断

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

        res = 0
        # 遍历两个哈希表,求最长和谐子序列长度
        for key in map1:
            l = map1[key]
            if sum(l) != key * len(l):
                res = max(res, len(l)) 
        for key in map2:
            l = map2[key]
            if sum(l) != key * len(l):
                res = max(res, len(l)) 
        return res

最后更新于