1:1, 2:3, 3:2, 5:1, 7:1

最长和谐子序列 题目描述 给定一个整数数组 nums ，要求找到其中最长的和谐子序列的长度。和谐子序列定义为：序列中的最大值和最小值的差正好为 1。注意，和谐子序列不要求连续，但要求元素在原数组中的顺序不变。 例如： 输入： [1,3,2,2,5,2,3,7] ，输出：5（因为最长的和谐子序列是 [3,2,2,2,3] ，最大值3和最小值2的差为1）。 输入： [1,2,3,4] ，输出：2（和谐子序列可能是 [1,2] 、 [2,3] 或 [3,4] ）。 解题思路 关键观察 ：和谐子序列只由两种相邻的数值组成（例如 x 和 x+1 ），且序列中所有元素必须是这两种值之一。 问题转化 ：对于每个可能的数值 x ，我们需要统计 x 和 x+1 在数组中出现的总次数，这个总数就是由 x 和 x+1 能构成的最长和谐子序列的长度。 动态规划预处理 ： 使用哈希表记录每个数值出现的次数。 遍历哈希表中的每个键 x ，如果 x+1 也存在，则计算 count[x] + count[x+1] ，并更新最大长度。 详细步骤 步骤1：统计频率 遍历数组 nums ，用哈希表 freq 记录每个数字出现的次数。 示例 [1,3,2,2,5,2,3,7] 的统计结果： 步骤2：遍历哈希表找相邻数值对 对于每个键 x ，检查 x+1 是否在哈希表中： 若存在，则和谐子序列长度为 freq[x] + freq[x+1] 。 若不存在，则跳过。 示例计算过程： x=1 ： x+1=2 存在，长度=1+3=4 x=2 ： x+1=3 存在，长度=3+2=5（最大） x=3 ： x+1=4 不存在，跳过 x=5 ： x+1=6 不存在，跳过 x=7 ： x+1=8 不存在，跳过 步骤3：输出最大值 最大长度为5，对应和谐子序列由数字2和3组成。 算法复杂度 时间复杂度：O(n)，遍历数组和哈希表各一次。 空间复杂度：O(n)，哈希表存储频率。 为什么这是线性动态规划？ 虽然本题解法以哈希表为主，但本质是 对频率的线性统计 ，并利用相邻数值关系递推最长长度。若将问题扩展为“允许差值不超过k的最长子序列”，则需用动态规划状态转移，但本题k=1时可直接用贪心统计。