最长和谐子序列

题目描述
给定一个整数数组nums，你需要找到其中最长的和谐子序列的长度。和谐子序列定义为：序列中的最大值和最小值的差正好为1。注意，子序列不要求连续，但要求元素在原数组中的相对顺序保持不变。

示例：
输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3] 或 [2,2,2,3,3]，最大值3和最小值2的差为1。

解题过程

1. 问题分析
和谐子序列的关键条件是最大值与最小值之差恰好为1。这意味着和谐子序列实际上只能由两种数字组成：比如x和x+1。整个序列必须全部由x和/或x+1构成，不能包含其他数字。

由于子序列不要求连续，我们可以自由选择原数组中满足数值条件(x或x+1)的元素，并保持它们的相对顺序。

2. 关键观察
对于任意一个可能的x值，和谐子序列的长度就等于数组中所有x的出现次数加上所有x+1的出现次数。

因此，问题转化为：找到所有相邻的整数对(x, x+1)，计算count(x) + count(x+1)，取最大值。

3. 哈希表解法
这是最直观的解法，时间复杂度O(n)，空间复杂度O(n)：

1. 使用哈希表统计每个数字出现的次数
2. 遍历哈希表中的每个键值x：
   • 如果x+1也在哈希表中，计算count(x) + count(x+1)
   • 更新最大长度
3. 返回找到的最大长度

def findLHS(nums):
    from collections import Counter
    count = Counter(nums)
    max_length = 0
    
    for num in count:
        if num + 1 in count:
            max_length = max(max_length, count[num] + count[num + 1])
    
    return max_length

4. 排序+双指针解法
如果不使用额外空间，可以用排序+双指针的方法：

1. 先将数组排序
2. 使用双指针维护一个窗口，保证窗口内的最大值-最小值 ≤ 1
3. 当差值正好为1时，更新最大长度

def findLHS(nums):
    nums.sort()
    left = 0
    max_length = 0
    
    for right in range(len(nums)):
        # 收缩左指针，直到窗口内差值 ≤ 1
        while nums[right] - nums[left] > 1:
            left += 1
        
        # 只有当差值正好为1时才更新结果
        if nums[right] - nums[left] == 1:
            max_length = max(max_length, right - left + 1)
    
    return max_length

5. 单次遍历的优化解法
我们可以在一次遍历中同时统计并计算：

def findLHS(nums):
    from collections import defaultdict
    count = defaultdict(int)
    max_length = 0
    
    for num in nums:
        count[num] += 1
        
        # 检查num-1和num+1是否存在
        if num - 1 in count:
            max_length = max(max_length, count[num] + count[num - 1])
        if num + 1 in count:
            max_length = max(max_length, count[num] + count[num + 1])
    
    return max_length

6. 算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)（哈希表存储）

7. 边界情况考虑

• 空数组：返回0
• 所有元素相同：返回0（因为没有差值为1的数对）
• 数组中既有(x, x+1)对，也有(y, y+1)对：取和最大的那个

这个问题的核心在于理解和谐子序列的本质——只能包含两个相邻的整数值，然后通过简单的计数统计就能解决问题。