LeetCode 题解工作台
最长和谐子序列
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。 给你一个整数数组 nums ，请你在所有可能的 子序列 中找到最长的和谐子序列的长度。 数组的 子序列 是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。 示例 1： 输入： nums …
5
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以用一个哈希表 记录数组 中每个元素出现的次数，然后遍历哈希表中的每个键值对 $(x, c)$，如果哈希表中存在键 $x + 1$，那么 中元素 和 $x + 1$ 出现的次数之和 $c + \textit{cnt}[x + 1]$ 就是一个和谐子序列，我们只需要在所有和谐子序列中找到最大的长度即可。 时间复杂度 ，空间复杂度 。其中 为数组 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
给你一个整数数组 nums ，请你在所有可能的 子序列 中找到最长的和谐子序列的长度。
数组的 子序列 是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
示例 1：
输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：
最长和谐子序列是 [3,2,2,2,3]。
示例 2：
输入：nums = [1,2,3,4]
输出：2
解释：
最长和谐子序列是 [1,2]，[2,3] 和 [3,4]，长度都为 2。
示例 3：
输入：nums = [1,1,1,1]
输出：0
解释：
不存在和谐子序列。
提示：
1 <= nums.length <= 2 * 104-109 <= nums[i] <= 109
解题思路
方法一：哈希表
我们可以用一个哈希表 记录数组 中每个元素出现的次数，然后遍历哈希表中的每个键值对 ，如果哈希表中存在键 ，那么 中元素 和 出现的次数之和 就是一个和谐子序列，我们只需要在所有和谐子序列中找到最大的长度即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def findLHS(self, nums: List[int]) -> int:
cnt = Counter(nums)
return max((c + cnt[x + 1] for x, c in cnt.items() if cnt[x + 1]), default=0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) to build the frequency map and O(k) to iterate through unique numbers, where k is the number of distinct elements. Space complexity is O(k) for the hash map. Sorting-based approaches would increase time to O(n log n), so hash-based counting is optimal for larger arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you know a way to avoid checking every possible subsequence?
- question_mark
Can you leverage a hash table to count occurrences and simplify the comparison?
- question_mark
How would you handle arrays where all elements are identical?
常见陷阱
外企场景- error
Forgetting that subsequences do not need to be contiguous, leading to incorrect slicing logic.
- error
Summing frequencies incorrectly or checking non-consecutive numbers, which produces invalid subsequences.
- error
Not returning 0 for arrays where no harmonious pair exists, e.g., all elements identical.
进阶变体
外企场景- arrow_right_alt
Return the actual longest harmonious subsequence array instead of just its length.
- arrow_right_alt
Modify the problem to find subsequences where the max and min differ by exactly k instead of 1.
- arrow_right_alt
Determine the number of distinct harmonious subsequences of maximum length.