8/3 每日一題(Python 返回最長的和諧序列-最大最小相差1的序列)

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

Given an integer array nums, return the length of its longest harmonious subsequence among all its possible subsequences.

A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

 

Example 1:

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

Example 2:

Input: nums = [1,2,3,4]
Output: 2

Example 3:

Input: nums = [1,1,1,1]
Output: 0

 

Constraints:

• 1 <= nums.length <= 2 * 104
• -109 <= nums[i] <= 109

class Solution:

    def findLHS(self, nums: List[int]) -> int:

        con_dict=Counter(nums)

#轉換成紀錄每個元素次數的字典,只需檢查key+1是否在字典中,如果存在就計算value

檢查是否為最長長度的和諧序列

       

        max_res=0

        for i,j in con_dict.items():

            if i+1 in con_dict:

                res=j+con_dict[i+1]

                max_res=max(res,max_res)

        return max_res