Lt594. 最长和谐子序列

594. 最长和谐子序列

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

示例 3：

输入：nums = [1,1,1,1]
输出：0

提示：

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

思路

先用 map 存储对应的数及出现次数，用 max 记录最长的元素数量。遍历每一个元素，将当前数加上 1 或减去 1 得到两个目标值 target，判断 map 中是否存在 target，取大的那一个 target 元素出现次数加上当前元素出现次数，更新 max。最后返回 max。

解答

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLHS = function (nums) {
  const map = new Map();
  for (const num of nums) map.set(num, map.has(num) ? map.get(num) + 1 : 1);
  const arr = [...map.entries()];
  let max = 0;
  for (let i = 0; i < arr.length; i++) {
    const [number, times] = arr[i];
    const [targetNumberA, targetNumberB] = [number + 1, number - 1];
    const [targetTimesA, targetTimesB] = [
      map.get(targetNumberA),
      map.get(targetNumberB),
    ];
    let res = 0;
    if (targetTimesA || targetTimesB) {
      res = Math.max(
        times + (Number.isInteger(targetTimesA) ? targetTimesA : 0),
        times + (Number.isInteger(targetTimesB) ? targetTimesB : 0)
      );
    }
    max = Math.max(res, max);
  }
  return max;
};