最长和谐子序列

题目链接

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例:

输入：nums = [1,3,2,2,5,2,3,7] 
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]

思路

解法一：

排序+滑动窗口法

  1. 先对数组进行排序
  2. 右指针遍历数组，左指针从0开始，若左右指针的差值大于1，则左指针右移，收缩区间
  3. 比较长度，取最大值
class Solution:
    def findLHS(self, nums: List[int]) -> int:
        nums.sort()
        i , ans = 0, 0
        for j in range(len(nums)):
            # 滑动窗口，收缩区间
            while i < j and nums[j] - nums[i] > 1: i += 1
            if nums[j] - nums[i] == 1:
                ans = max(ans, j - i + 1)
        return ans