最长和谐子序列（Longest Harmonious Subsequence）

题目描述
给定一个整数数组 nums，定义“和谐子序列”为数组中最大值与最小值之差恰好为 1 的子序列。子序列不要求连续，但要求元素在原数组中的相对顺序不变。请你找出并返回最长和谐子序列的长度。

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

解题过程

1. 问题分析

• 和谐子序列的元素只能有两种值，设较小值为 x，较大值为 x+1。
• 子序列中只能包含这两种值，其他值不能出现。
• 子序列长度等于这两种值在子序列中出现的总次数。
• 由于子序列不要求连续，我们只需在原数组中选出所有等于 x 或 x+1 的数，并保持它们在原数组中的相对顺序即可。
• 关键观察：如果数组中存在多个值为 x 和 x+1 的元素，我们可以全部取出来，这样一定构成一个和谐子序列（因为值只有两种，且差为1）。

2. 思路转化

问题转化为：
对于数组中的每一个数 x，我们需要知道：

• count(x)：值为 x 的元素个数。
• count(x+1)：值为 x+1 的元素个数。

则 x 对应的和谐子序列长度为 count(x) + count(x+1)。
遍历所有可能的 x，取最大值。

3. 基础解法（哈希表计数）

最直接的方法：

1. 使用哈希表统计每个数字的出现次数。
2. 遍历哈希表中的每个键 num，检查 num+1 是否也在哈希表中，如果在，则计算 count[num] + count[num+1]，更新最大值。

时间复杂度：O(n)
空间复杂度：O(n)

4. 动态规划思路的引入

为什么这个问题可以视为线性动态规划？

• 如果我们按原数组顺序考虑，定义状态 dp[i] 为以 nums[i] 结尾的最长和谐子序列长度，会发现难以直接转移，因为和谐子序列要求所有元素只有两种值，且差为1，这并不适合传统的“以 i 结尾”的 LIS 型状态定义。

但是，我们可以换一种动态规划的角度：
定义两个哈希表（或数组映射）：

• dp_up[x]：以值 x 结尾，且子序列中最大值是 x、最小值是 x-1 的最长和谐子序列长度。
• dp_down[x]：以值 x 结尾，且子序列中最大值是 x+1、最小值是 x 的最长和谐子序列长度。

这样定义虽然可行，但实现较复杂。实际上，本题更简单的动态规划思路是排序后转化为相邻元素的计数问题。

5. 排序 + 滑动窗口（类似 DP 的连续子序列思想）

1. 将数组排序。
2. 问题变为：在排序数组中找一个子序列（实际是连续段，因为排序后相同的数在一起，且我们只取两种值），使得两种值相差 1，且包含这两种值的所有出现。
3. 排序后，我们可以用滑动窗口保证窗口内最大值与最小值差为 1：
   • 设置左右指针 left 和 right，初始为 0。
   • 右指针右移，直到窗口内最大值与最小值差 > 1。
   • 若差 == 1，计算窗口长度，更新答案。
   • 移动左指针以保持差 ≤ 1。

这个滑动窗口的过程可以看作是在有序数组中找满足条件的最长连续子数组，虽然子序列不要求连续，但排序后相同值的元素聚在一起，我们可以取所有这两种值的元素，因此连续子数组的长度就是和谐子序列的长度。

6. 线性动态规划的另一种视角（类似 LIS 但有限制）

如果坚持用原始数组顺序的 DP，可以这样设计：

• 定义 dp[i] 为以 nums[i] 结尾的和谐子序列长度。

• 我们需要知道这个子序列的最小值和最大值。

• 更可行的方案：
  设 dp_val_max[x] 表示以值 x 结尾且当前子序列中最大值是 x 的最长和谐子序列长度。
  设 dp_val_min[x] 表示以值 x 结尾且当前子序列中最小值是 x 的最长和谐子序列长度。

  转移：
  遇到一个数 num：

  • 它可以接在值为 num-1 结尾的子序列后面，此时子序列最大值变为 num，最小值是 num-1，所以更新 dp_val_max[num] = max(dp_val_max[num], dp_val_min[num-1] + 1)？
    注意：dp_val_min[num-1] 表示以 num-1 结尾且最小值是 num-1 的和谐子序列长度，接上 num 后，最小值仍是 num-1，最大值是 num，这是和谐子序列。
  • 同理，它可以接在值为 num+1 结尾的子序列后面，此时最小值是 num，最大值是 num+1，更新 dp_val_min[num] = max(dp_val_min[num], dp_val_max[num+1] + 1)。

  还需要考虑自己单独开始的情况：dp_val_max[num] 和 dp_val_min[num] 至少为 1（只取自己一个数，但和谐子序列要求至少两个不同值，所以单独一个数不计入答案，只在转移时作为起点）。

  这样最终答案不是 dp_val_max[num] 或 dp_val_min[num] 的最大值，而是满足最大值与最小值差 1 的成对 dp 状态之和？

这种 DP 实现较复杂，且需要处理好单独一个数不计入答案的情况。

7. 推荐解法（哈希表计数）

由于和谐子序列不要求连续，我们只需考虑两种值的所有出现次数，因此直接计数即可：

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

为什么这是动态规划思想？

• 我们可以将 count[num] 视为“以值 num 作为较小值时的候选长度的一部分”。
• 状态转移是隐含的：对于每个 num，我们只需要 num+1 的计数，这是一个“依赖相邻值”的递推关系。
• 本质上，我们是在所有可能的 (x, x+1) 值对上做计算，取最大值。

8. 边界情况

• 数组中所有元素相同 → 没有差值恰好为1的两类数 → 结果为0。
• 数组长度为 0 或 1 → 结果为0。

9. 总结

本题虽然是“最长和谐子序列”，但因其特殊限制（差值恰好为1、不要求连续），可以简化为哈希表计数 + 相邻键值对求和取最大值的问题，时间复杂度 O(n)，空间复杂度 O(n)。

这个解法利用了“子序列不要求连续”的特性，将问题转化为对值域的统计，从而避免了复杂的序列型 DP 设计。