【Leetcode 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 * 104
• -109 <= nums[i] <= 109

哈希表 

//哈希表
function findLHS(nums: number[]): number {
  const numsMap = new Map<number, number>();
  let res = 0;
  //保存每个数出现的次数
  for (const num of nums) {
    const v = (numsMap.get(num) || 0) + 1;
    numsMap.set(num, v);
  }

  numsMap.forEach((_, key) => {
    //有和谐数，则计算和谐数组的长度
    if (numsMap.has(key + 1)) {
      const newRes = numsMap.get(key)! + numsMap.get(key + 1)!;
      res = Math.max(res, newRes);
    }
  });
  return res;
}

滑动窗口

//滑动窗口
function findLHS(nums: number[]): number {
  nums.sort((a, b) => a - b);
  let res = 0;
  let begin = 0;
  for (let end = 0; end < nums.length; end++) {
    //右边界与左边界的值相差大于1，则缩小窗口左侧
    while (nums[end] - nums[begin] > 1) {
      begin++;
    }
    //右边界与左边界的值相差等于1，比较之前窗口和此窗口，保存大窗口的值
    while (nums[end] - nums[begin] === 1) {
      res = Math.max(res, end - begin + 1);
    }
  }
  return res;
}