LeetCode 594. 最长和谐子序列
题目描述
题意分析
从数组中保留部分元素，顺序不变，得到最大值与最小值恰好相差一的最长子序列，返回它的长度。子序列不要求位置连续，可以跳过中间元素。
条件是差恰好为一，不是差不超过一，因此必须同时出现两个不同值。只有一种数值的序列不算和谐；不存在相邻两种整数时，答案为零。
解法：哈希计数枚举相邻值
核心思路
[!blue]
若选定子序列的最小值为整数
x，最大值就必须为x + 1。两者之间没有其他整数，因此这个候选只能包含这两种值，并且每一种至少选择一次。对这一对值，可以取出它们在原数组中的全部出现。按原顺序保留这些位置，天然就是子序列；多保留一个
x或x + 1不会改变最大最小值，所以取全时长度最大，等于count[x] + count[x + 1]。因此先统计每个值的频次，再把每个不同值当作可能的最小值，检查大一的邻值是否存在。存在才组成合法候选，并以频次和更新最大长度。每一对相邻值都有唯一的较小值，只向上查找一次就能覆盖全部候选。
解题步骤
- 遍历数组，统计每个数值出现次数。
- 将答案初始化为零，枚举哈希表中的每个值
x。- 只有
x + 1也存在时，才计算两种值的频次和。- 对全部合法候选取最大值并返回；没有候选时保留零。
代码实现
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个元素，再扫描至多n个不同键，哈希查询平均为常数。- 空间复杂度：$O(u)$，
u为不同数值的数量，最坏等于n。
关键点总结
[!green]
- 整数极差恰好为一，直接将候选限制为两种相邻整数。
- 固定这两种值后，保留全部出现既合法又最长，频次足够求答案。
- 子序列可以跳过其他值，仍按原顺序保留，不需要真的排序或构造结果。
- 相邻两类必须同时存在，单类频次再高也不能单独成为答案。
易错点总结
[!yellow]
- 将条件理解成差不超过一，错误接受只含相同值的序列。
- 邻值不存在时仍用自身频次更新答案，实际候选的极差为零。
- 枚举候选后累加各对长度，会把不同取值范围混在一起，应该取最大值。
- 要求元素在原数组中连续，求成了子数组，丢掉可以跨过无关元素的更长选择。
- 只统计不同值是否出现，忽略同值的多次出现都能加入合法子序列。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 128. 最长连续序列 | 中等 | 原题要求存在连续数值段且忽略重复，本题只允许最大最小差恰为1，需相邻两个值的频次和。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！