首页 > itarticle > PU Longest Harmonious Subsequence

PU Longest Harmonious Subsequence

admin 11月 12, 2020 0

Jan 01, 1970

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

The length of the input array will not exceed 20,000.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Python Solution 1:

class Solution:
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        d = list(collections.Counter(nums).items())
        d.sort()
        res = 0;
        for i in range(1, len(d)):
            if d[i - 1][0] + 1 == d[i][0]:
                res = max(res, d[i][1] + d[i - 1][1])
        return res;

Python Solution 2:

class Solution:
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        d = collections.Counter(nums)
        for key in d:
            if key + 1 in d:
                res = max(res, d[key] + d[key + 1])
        return res

Summary:

nothing to say

LeetCode: 594. Longest Harmonious Subsequence