LeetCode 594. 最长和谐子序列

2023-03-22 HGNULB 约 8 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 594. 最长和谐子序列

题意分析

题目定义「和谐数组」为最大值与最小值之差恰好等于 1 的数组，要在 nums 的所有子序列里找出最长的和谐子序列，返回它的长度。

两个词必须抠清楚。第一个是「子序列」——它只要求保持相对顺序，不要求连续，可以任意挑选下标。既然可以任意挑，原数组的顺序就完全不影响答案，剩下有意义的信息只有「每个值出现了多少次」。这一步把问题从「在序列上找区间」降级成了「在值域上做统计」。

第二个是「恰好等于 1」，而不是「不超过 1」。差为 0（全部相同）不算和谐，所以答案必须同时包含两种不同的值。既然极差正好是 1，这个子序列里能出现的值就只有 x 和 x + 1 两种——中间不可能塞进第三种值。而既然是子序列且顺序无关，一旦选定 x，最优做法必然是把 x 和 x + 1 的全部出现都收进来。

于是答案的形状被完全确定了：它一定形如「某个 x 的出现次数 + x + 1 的出现次数」，而且要求两者的次数都大于 0。

边界：数组里可能根本不存在相差 1 的两个值（例如 [1, 1, 1, 1]），此时不存在任何和谐子序列，答案是 0 而不是 4；数组长度可能为 1；数值范围到 $10^9$，值本身很稀疏，不能开值域数组。

解法：哈希计数枚举相邻值

核心思路

暴力做法是枚举子序列，或者退一步枚举「最小值取哪个数」再扫一遍数组统计，前者指数级不可行，后者是 $O(n^2)$。$O(n^2)$ 的瓶颈在于：为了知道值 x 和 x + 1 各出现多少次，每次都要重新扫描整个数组，而这个统计对所有 x 其实可以一次性算完。

由题意分析已经得到，答案必定等于某对相邻值的频次之和。所以只需要两样东西：一张「值 → 出现次数」的表，以及对表中每个键去查它的后继键是否存在。哈希表让这两件事都变成均摊 $O(1)$。

这里要显式写清楚的判定条件是：只有当 count[x] 和 count[x + 1] 同时存在（都大于 0）时，count[x] + count[x + 1] 才是一个合法候选。这条判定正是「极差恰好为 1」的直接翻译——少了任何一边，极差就变成 0，不再和谐。答案初始化为 0，若一个候选都没产生，返回的就是 0，这与「不存在和谐子序列」的语义天然吻合。

枚举方向只查 x + 1 不查 x - 1，不会遗漏：任意一对相邻值 (x, x + 1) 都会在枚举到较小的那个键 x 时被恰好检查一次。只往一个方向查还顺带避免了同一对被算两遍。

值域到 $10^9$，所以只能用哈希表而不能用计数数组——这是本题选择哈希而非桶计数的直接理由。另一条可行路径是先排序再用滑动窗口维持「极差 ≤ 1」的区间，但它引入了排序的对数因子，且窗口收缩与答案更新时机容易写错，不如计数法直接。

解题步骤

第一遍遍历 nums，把每个值的出现次数记进哈希表：这一遍把「顺序」信息彻底丢掉，只留下频次。用 getOrDefault(num, 0) + 1（Go 里直接 count[num]++，零值为 0）避免对首次出现的键做特判。

res 初始化为 0：0 既是「长度」的合法下界，也是「不存在和谐子序列」时该返回的值。初始化成 Integer.MIN_VALUE 或 1 都会让无解用例出错。

第二遍遍历哈希表的键，而不是再遍历 nums：遍历键保证每个不同的值只被考察一次。若改成遍历原数组，重复值会带来重复计算，虽不影响正确性但会退化成 $O(n)$ 次查表——在这题上无所谓，但换成需要去重的场景就会出问题。

对每个键 num 检查 num + 1 是否在表中：这一步是「相邻值必须同时存在」的落地。用 containsKey 而不是 get(num + 1) != null 之后再拆箱，能避免不必要的装箱开销与空指针风险。

存在则用 count[num] + count[num + 1] 更新 res：两个频次直接相加就是这一对能凑出的最长和谐子序列长度，不需要考虑取舍——多取一个元素不会破坏极差为 1 的性质，所以全取必然最优。

遍历完返回 res。

以 nums = [1, 3, 2, 2, 5, 2, 3, 7] 走一遍（期望 5，对应子序列 [3, 2, 2, 2, 3]）。

第一遍统计完得到 count = {1: 1, 3: 2, 2: 3, 5: 1, 7: 1}。

第二遍逐键考察（哈希表顺序不定，这里按值从小到大列）：键 1，查到 2 存在，候选 1 + 3 = 4，res 从 0 更新为 4，对应子序列 [1, 2, 2, 2]；键 2，查到 3 存在，候选 3 + 2 = 5，res 更新为 5；键 3，查 4 不存在，跳过——注意 3 和 2 这一对已经在键 2 那轮算过了，只往上查不会漏；键 5，查 6 不存在，跳过；键 7，查 8 不存在，跳过。

返回 res = 5。

再看一个无解用例 nums = [1, 1, 1, 1]：count = {1: 4}，唯一的键 1 查不到 2，一个候选都没产生，返回初值 0。如果这里错误地把「同一个值出现多次」也算作和谐，就会返回 4。

代码实现

class Solution {
    // 和谐子序列的最大值与最小值差正好为 1，因此候选只能由 x 和 x + 1 两种值组成。
    public int findLHS(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        int res = 0;
        for (int num : count.keySet()) {
            if (count.containsKey(num + 1)) {
                res = Math.max(res, count.get(num) + count.get(num + 1));
            }
        }

        return res;
    }
}

func findLHS(nums []int) int {
    // 和谐子序列的最大值与最小值差正好为 1，因此候选只能由 x 和 x + 1 两种值组成。
    count := make(map[int]int)
    for _, num := range nums {
        count[num]++
    }

    res := 0
    for num, c := range count {
        if v, ok := count[num+1]; ok {
            if c+v > res {
                res = c + v
            }
        }
    }

    return res
}

复杂度分析

时间复杂度：$O(n)$。凭什么：第一遍遍历数组做 n 次均摊 $O(1)$ 的哈希写入；第二遍遍历的是哈希表的键，键数不超过 n，每个键做一次均摊 $O(1)$ 的查询与常数次比较。

空间复杂度：$O(n)$。凭什么：哈希表最多存放 n 个互不相同的键值对（数组元素全不相同时取到上界）。数值范围到 $10^9$ 而元素只有 $10^4$ 个，用哈希表而非值域数组正是为了让空间跟着元素个数走而不是跟着值域走。

关键点总结

看到「子序列 + 只关心最值 / 极差」，先问自己顺序还重不重要；不重要就立刻把问题从序列问题转成频次统计问题，这一步往往直接砍掉一个数量级。

「极差恰好为 1」把候选集合压缩成了「相邻整数对」，答案的形状被约束成 count[x] + count[x+1]——先推出答案的形状再设计算法，比先想数据结构更可靠。

枚举成对关系时只往单一方向查（只查 x + 1 不查 x - 1），既不遗漏也不重复，是处理对称关系的通用去重技巧。

值域远大于元素个数时用哈希表而非计数数组，这个取舍要能在面试中一句话说清：空间跟着元素规模走，不跟着值域走。

无解时返回 0 由「答案初值取 0 且只在找到合法对时更新」自然保证，不需要额外的特判分支——好实现的标志是边界落进主逻辑。

易错点总结

把「极差不超过 1」当成判定条件：nums = [1, 1, 1, 1] 会返回 4，正确答案是 0，因为全相同的数组极差为 0 不算和谐。

res 初始化为 1 或数组长度：nums = [1, 1, 1, 1] 会返回非零值；初值只能是 0。

查到 num + 1 不存在时仍然用 count.get(num) 更新答案：nums = [1, 1, 1, 1] 里 count[1] = 4 会被当成候选，返回 4。

既查 num + 1 又查 num - 1 且都更新：结果虽不会错，但 nums = [1, 2] 这类用例会把同一对算两遍；一旦有人顺手把两次结果相加就会返回 4 而不是 2。

用 count.get(num + 1) 直接参与运算而不先判存在：Java 里返回 null 拆箱抛空指针异常，nums = [1, 3] 立刻崩溃；Go 里返回零值 0，会把 [1, 3] 算成候选 1 + 0 = 1，返回 1 而不是 0。

第二遍遍历原数组而不是哈希表的键，并把每次命中都累加而非取最大：nums = [1, 2, 2] 会把键 1 的候选重复计入，得到远大于 3 的值。

误以为子序列必须连续，改用原地滑动窗口而不排序：nums = [1, 3, 2, 2, 5, 2, 3, 7] 里合法元素被 5 和 7 隔断，会返回 3 之类的偏小值，正确答案是 5。

改用数组计数且直接以数值作下标：nums = [1000000000] 会申请十亿长度的数组，直接内存溢出——这正是值域到 $10^9$ 时必须用哈希表的原因。

排序滑窗版把更新时机放在差值 ≤ 1 时：nums = [1, 1, 1] 窗口铺满整个数组、差值为 0 也被计入，返回 3 而不是 0。

排序滑窗版收缩时用 if 而非 while：nums = [1, 1, 5, 5] 右指针从 1 跳到 5 时一次收缩不足以让差值回到 1 以内，窗口非法却仍参与答案更新。

相似题目

题目	难度	考察点
128. 最长连续序列	中等	同样在值域上找相邻整数，但要串起任意长的连续段，需从段首启动才能保证线性
1. 两数之和	简单	边遍历边查表，查的是「配对值是否已出现」而非频次，且需返回下标而非长度
347. 前 K 个高频元素	中等	统计频次后要按频次排序取前 K，需配合堆或桶排序，而非只查相邻键
219. 存在重复元素 II	简单	哈希表存的是下标而非次数，判定条件涉及位置距离，顺序信息不能丢
645. 错误的集合	简单	值域恰好是 `1..n`，可以用原地负号标记把空间压到 $O(1)$，不必开哈希表
1200. 最小绝对差	简单	差值不固定为 1 而是要先求出最小差，必须排序后比较相邻元素
350. 两个数组的交集 II	简单	频次统计用于两数组求交，取的是两边计数的较小值而非求和
383. 赎金信	简单	频次统计用于逐项做「够不够」的比较，字符集有限时可退化为定长数组