最长和谐子序列

题目描述
和谐子序列是指一个序列中最大值和最小值的差恰好等于1。给定一个整数数组nums，请找出其中最长的和谐子序列的长度。

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

解题过程

第一步：理解问题本质
和谐子序列的关键特征是只包含两种数字，且这两种数字的差为1。注意这不一定要求序列连续，但要求元素顺序与原数组一致（子序列特性）。

关键观察：和谐子序列实际上就是由两个相邻整数（比如x和x+1）组成的子序列。

第二步：基础解法思路
最直接的思路：

1. 统计每个数字出现的次数
2. 对于每个数字x，检查x+1是否存在
3. 如果存在，则和谐子序列长度为count(x) + count(x+1)
4. 找出所有这样的组合中的最大值

第三步：哈希表统计

from collections import Counter

def findLHS(nums):
    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

时间复杂度分析：O(n)，其中n为数组长度
空间复杂度分析：O(n)，用于存储哈希表

第四步：详细示例演示
以nums = [1,3,2,2,5,2,3,7]为例：

统计结果：

• 1: 出现1次
• 2: 出现3次
• 3: 出现2次
• 5: 出现1次
• 7: 出现1次

检查相邻数字组合：

• 1和2：1+3=4
• 2和3：3+2=5 ✓（最大值）
• 3和4：4不存在
• 5和6：6不存在
• 7和8：8不存在

第五步：边界情况考虑

1. 空数组：返回0
2. 所有数字相同：没有相邻数字，返回0
3. 多个和谐子序列：取最大值
4. 负数情况：处理方式相同

第六步：算法优化思考
上面的解法已经是最优解，但可以进一步优化遍历过程：

• 只需要遍历哈希表中的键，避免重复计算
• 确保每个数字对只计算一次

第七步：验证正确性
通过多个测试用例验证：

• [1,1,1,1] → 0（没有相邻数字）
• [1,2,3,4] → 2（如[1,2]或[2,3]或[3,4]）
• [1,3,5,7,9] → 0（数字间隔大于1）

总结
这个问题虽然简单，但体现了动态规划思想的核心：将复杂问题分解为简单的子问题（统计频率 + 组合检查）。通过哈希表预处理，我们避免了O(n²)的暴力解法，实现了线性时间复杂度。