0594. 最长和谐子序列【简单】

• 1. 📝 题目描述
• 2. 🫧 评价
• 3. 🎯 s.1 - 哈希表统计法
• 4. 🎯 s.2 - 排序后滑动窗口

1. 📝 题目描述

• leetcode

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 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

2. 🫧 评价

• s.1 - 哈希表统计法 时间更优
• s.2 - 排序 + 双指针 空间更优

3. 🎯 s.1 - 哈希表统计法

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLHS = function (nums) {
  // 统计每个数字出现的次数
  const countMap = new Map()
  for (const num of nums) {
    countMap.set(num, (countMap.get(num) || 0) + 1)
  }

  let maxLength = 0

  // 检查每个数字及其相邻数字
  for (const [num, count] of countMap) {
    // 如果 num+1 存在，则可以组成和谐子序列
    if (countMap.has(num + 1)) {
      maxLength = Math.max(maxLength, count + countMap.get(num + 1))
    }
  }

  return maxLength
}

• 时间复杂度：$O(n)$
  • 遍历数组统计频次需要 $O(n)$ 时间
  • 遍历哈希表检查相邻元素需要 $O(k)$ 时间，其中 $k$ 是不同元素的个数，最坏情况下 $k=n$
  • 总体时间复杂度为 $O(n)$
• 空间复杂度：$O(k)$
  • 需要哈希表存储每个元素的出现次数，最坏情况下需要 $O(n)$ 空间
• 
• 解题思路
  • 解决这个问题的关键是理解和谐子序列的定义：只包含两种数值，且它们相差为 1（如 x 和 x+1）
  • 核心步骤：
    1. 统计每个数字出现的频次
    2. 对于每个数字 x，检查 x+1 是否存在
    3. 如果存在，则 x 和 x+1 组成的子序列长度为 count(x) + count(x+1)
    4. 找到所有这样的组合中的最大长度

4. 🎯 s.2 - 排序后滑动窗口

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLHS = function (nums) {
  nums.sort((a, b) => a - b)

  let maxLength = 0
  let left = 0

  for (let right = 0; right < nums.length; right++) {
    // 如果差值超过1，移动左指针
    while (nums[right] - nums[left] > 1) {
      left++
    }

    // 如果差值正好为1，更新最大长度
    if (nums[right] - nums[left] === 1) {
      maxLength = Math.max(maxLength, right - left + 1)
    }
  }

  return maxLength
}

• 时间复杂度：$O(n\log n)$
  • 排序操作需要 $O(n\log n)$ 时间
  • 双指针遍历需要 $O(n)$ 时间
  • 总体时间复杂度为 $O(n\log n)$
• 空间复杂度：$O(1)$
  • 只使用了常数级别的额外空间（不考虑排序算法的额外空间）
•