哈希算法题目：最长和谐子序列 题目描述： 和谐子序列定义为一个数组中的子序列（元素不一定连续），其中最大值和最小值的差恰好为 1。给定一个整数数组 nums ，你需要返回最长的和谐子序列的长度。如果不存在这样的子序列，返回 0。 例如： 输入：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 的元素个数之和最大。 示例分析： nums = [ 1,3,2,2,5,2,3,7 ] 可能的数值对： 值 2 和 3（差为 1），出现次数：2 出现 3 次，3 出现 2 次，总和为 5。 值 1 和 2：1 出现 1 次，2 出现 3 次，总和为 4。 值 3 和 4：3 出现 2 次，4 出现 0 次，总和为 2。 最大长度为 5。 第二步：选择数据结构 我们需要高效统计每个数字的出现次数，并快速查找相邻数值的计数。 哈希表 是理想选择： 键：数组中的数字 值：该数字在数组中出现的次数 步骤： 遍历数组，用哈希表记录每个数字的出现次数。 遍历哈希表的键，对每个键 key ，检查 key+1 是否在哈希表中： 如果存在，计算 count(key) + count(key+1) ，更新最大长度。 返回最大长度。 第三步：详细步骤说明 构建频率哈希表 遍历数组 nums ，对每个数字 num ： 如果 num 不在哈希表中，插入 num 并设值为 1。 如果已存在，将其值加 1。 示例：nums = [ 1,3,2,2,5,2,3,7 ] 哈希表：{1:1, 3:2, 2:3, 5:1, 7:1} 遍历哈希表寻找和谐对 初始化 max_len = 0 。 对哈希表中的每个键 key ： 检查 key+1 是否在哈希表中。 如果在，计算当前长度 = hash[key] + hash[key+1] 。 更新 max_len = max(max_len, 当前长度) 。 注意：只需检查 key+1 ，因为 key 和 key-1 的情况会在遍历到 key-1 时覆盖，避免重复计算。 返回结果 遍历结束后， max_len 即为答案。 第四步：边界与特殊情况 空数组：返回 0。 数组元素相同（如 [ 1,1,1 ]）：没有差为 1 的数值对，返回 0。 数组包含负数：哈希表可正常处理。 时间复杂度：O(n)，n 为数组长度，需遍历数组建哈希表，再遍历哈希表键（键数量 ≤ n）。 空间复杂度：O(n)，存储哈希表。 第五步：示例推导 以 nums = [ 1,3,2,2,5,2,3,7 ] 逐步推导： 建哈希表：{1:1, 3:2, 2:3, 5:1, 7:1} 遍历哈希表键： 键 1：检查 2 存在，长度 = 1+3=4，max_ len=4 键 3：检查 4 不存在，跳过 键 2：检查 3 存在，长度 = 3+2=5，max_ len=5 键 5：检查 6 不存在，跳过 键 7：检查 8 不存在，跳过 返回 max_ len=5 第六步：扩展思考 如果要求输出和谐子序列本身（而不仅是长度），可以在哈希表基础上记录位置，但题目只需长度。 可以优化到一次遍历：在遍历数组统计频率时，同时检查当前数字的相邻值频率，但需要注意数字顺序，通常两次遍历更清晰。 第七步：总结 本题核心是利用哈希表统计频次，再通过相邻键的查找确定和谐对的最大总频次。哈希表提供了 O(1) 的查找效率，使整体时间复杂度保持在 O(n)，是处理此类“频次统计+相邻关系”问题的典型方法。