首页 > itarticle > algorithm notes: leetcode#594 longest harmonious subsequence

algorithm notes: leetcode#594 longest harmonious subsequence

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

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 implementation

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;
    }
}

Time complexity

O(n).

Space complexity

O(n).

Link

594. Longest Harmonious Subsequence
(中文版) 算法笔记: 力扣#594 最长和谐子序列