594. 最长和谐子序列

🟢   🔖  数组 哈希表 计数 排序 滑动窗口  🔗 力扣 LeetCode

题目

We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1.

Given an integer array nums, return the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:

Input: nums = [1,3,2,2,5,2,3,7]

Output: 5

Explanation:

The longest harmonious subsequence is [3,2,2,2,3].

Example 2:

Input: nums = [1,2,3,4]

Output: 2

Explanation:

The longest harmonious subsequences are [1,2], [2,3], and [3,4], all of which have a length of 2.

Example 3:

Input: nums = [1,1,1,1]

Output: 0

Explanation:

No harmonic subsequence exists.

Constraints:

• 1 <= nums.length <= 2 * 10^4
• -10^9 <= nums[i] <= 10^9

题目大意

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是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 * 10^4
• -10^9 <= nums[i] <= 10^9

解题思路

1. 使用哈希表统计频次：

   • 遍历数组 nums，将每个元素的出现次数记录在 Map 中，方便后续查找元素的频次。

2. 查找相邻数字：

   • 遍历 Map 中的所有元素 key，对于每个 key：
     • 检查 key + 1 是否存在于 Map 中（保证最大值和最小值之差为 1）。
     • 如果存在，则将 key 和 key + 1 的出现次数相加，作为当前和谐子序列的长度。
   • 使用一个变量 maxLength 记录遍历过程中找到的最大和谐子序列的长度。

3. 返回结果：

   • 遍历完成后，maxLength 即为最长的和谐子序列的长度。

复杂度分析

• 时间复杂度：O(n + m)
  • 遍历数组一次统计频次：O(n)。
  • 遍历 Map 的键：O(m)（m 是数组中唯一数字的个数）。
  • 总时间复杂度为 O(n + m)。
• 空间复杂度：O(m)，使用了 Map 记录频次。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLHS = function (nums) {
	let map = new Map(); // 用于统计每个数字的出现频次

	// 统计数字的频次
	for (let num of nums) {
		map.set(num, (map.get(num) || 0) + 1);
	}

	let maxLength = 0; // 记录最长和谐子序列的长度

	// 遍历哈希表，查找和谐子序列
	for (let key of map.keys()) {
		// 检查 key + 1 是否存在
		if (map.has(key + 1)) {
			// 计算当前和谐子序列的长度
			maxLength = Math.max(maxLength, map.get(key) + map.get(key + 1));
		}
	}

	// 返回最长和谐子序列的长度
	return maxLength;
};