0594. Longest Harmonious Subsequence
====================================
题目信息
--------
:题号: 0594
:难度: Easy
:主题: 数组、子序列、最大值最小值、频次统计
:原题: `LeetCode 0594 `_
:重点: 子序列无需连续、最大值与最小值之差必须恰好为 1、只有一种数值时不合格
题目重述
--------
给定整数数组 ``nums``,寻找最长的和谐子序列。和谐子序列要求所选元素中的最大值与最小值之差恰好等于 ``1``。
子序列可以删除原数组中的任意元素,但保留元素的相对顺序不能改变;只需返回最大长度。若不存在同时包含两个相邻整数值的子序列,返回 ``0``。
自建示例
--------
相邻两种数值共同组成最长答案:
.. code-block:: text
输入:nums = [1,2,2,3,3,3]
输出:5
解释:选择所有 2 和 3,可得到长度 5 的子序列,最大值与最小值之差为 1。
只有一种数值:
.. code-block:: text
输入:nums = [4,4,4]
输出:0
解释:任意非空子序列的最大值与最小值之差都是 0,不满足恰好为 1。
统计相邻数值的频次总和
----------------------
和谐子序列只关心选出的数值集合,且允许从原数组删除任意元素,所以对于一对 ``x`` 和 ``x + 1``,可以把它们的全部出现位置都选入子序列。统计每个数值的频次,再枚举每个 ``x`` 与 ``x + 1`` 的频次和即可。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int findLHS(std::vector& nums) {
std::unordered_map frequency;
for (int value : nums) ++frequency[value];
int answer = 0;
for (const auto& [value, count] : frequency) {
auto next = frequency.find(value + 1);
if (next != frequency.end()) {
answer = std::max(answer, count + next->second);
}
}
return answer;
}
};
代码分析
--------
任意合法答案的最小值和最大值必须恰好是 ``x`` 与 ``x + 1``,同一数值的所有出现位置都不会破坏这个条件,因此该数值对的最大贡献就是两种频次之和。哈希表统计和枚举均为平均 ``O(n)``,额外空间复杂度为 ``O(u)``,其中 ``u`` 是不同数值的数量。