594. 最长和谐子序列

;(function () {
  /**
   * 594. 最长和谐子序列
   * 和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
   * 现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
   * 数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
   *
   * 输入：nums = [1,3,2,2,5,2,3,7]
   * 输出：5
   * 解释：最长的和谐子序列是 [3,2,2,2,3]
   *
   * 输入：nums = [1,2,3,4]
   * 输出：2
   *
   * 输入：nums = [1,1,1,1]
   * 输出：0
   *
   */

  function findLHS(nums: number[]): number {
    // 方法一：枚举？滑动窗口？
    // nums.sort((a, b) => a - b);
    // let s = 0;
    // let res = 0;
    // for (let e = 0; e < nums.length; e++) {
    //     while (nums[e] - nums[s] > 1) {
    //         s++
    //     }
    //     if (nums[e] - nums[s] === 1) {
    //         res = Math.max(res, e - s + 1)
    //     }
    // }
    // return res

    // 方法二： 哈希表
    let cns = new Map()
    let res = 0
    for (const num of nums) {
      cns.set(num, (cns.get(num) || 0) + 1)
    }
    cns.forEach((value: number, key: number) => {
      if (cns.get(key + 1)) {
        res = Math.max(res, cns.get(key) + cns.get(key + 1))
      }
    })
    return res
  }

  const nums = [1, 3, 2, 2, 5, 2, 3, 7]
  console.log(findLHS(nums))
})()