首页 > itarticle > 算法笔记: 力扣#594 最长和谐子序列

算法笔记: 力扣#594 最长和谐子序列

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

class (object):
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        counter = dict()
        res = 0
        for num in nums:
            counter[num] = counter.get(num, 0)+1
        for key, val in counter.items():
            if key+1 in counter:
                res = max(res, counter[key+1]+val)  
        return res

Java 实现

class  {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> counter = new HashMap<>();
        int res = 0;
        for(int num : nums){
            counter.put(num, counter.getOrDefault(num, 0)+1);
        }
        for(int num : counter.keySet()){
            if(counter.containsKey(num+1)){
                int curRes = counter.get(num)+counter.get(num+1);
                res = curRes > res ? curRes : res;
            }
        }
        return res;
    }
}

时间复杂度

O(n).

空间复杂度

O(n).

链接

594. Longest Harmonious Subsequence
594. 最长和谐子序列
 (English version) Algorithm Notes: Leetcode#594 Longest Harmonious Subsequence