算法-每日一题（DAY12）最长和谐子序列

1.题目链接：

594. 最长和谐子序列 - 力扣（LeetCode）

2.题目描述：

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

3.解题思路：

我们可以通过哈希表的方式，利用元素频率统计来求解数组中的最长和谐子序列。首先，创建一个哈希表 cnt 来记录每个数字在数组中的出现频次。接着，遍历 nums 数组，对于每一个数字 num，将其在 cnt 中的计数加 1。然后，遍历哈希表中的每一个键值对，检查是否存在一个比当前键大 1 的数字。如果存在这样的数字，说明这两个数字可以组成一个和谐子序列，此时更新最大和谐子序列的长度 res，即更新为当前和谐子序列长度 val + cnt[key + 1] 的较大值。最后，返回最长的和谐子序列长度 res。通过这种方式，代码实现了高效的查找和更新，从而得到数组中最长和谐子序列的长度。

4.题解代码：

class Solution {
public:
    int findLHS(vector<int>& nums) 
    {
        unordered_map<int, int>cnt;
        //创建哈希表cnt
        int res = 0;
        //定义一个变量res,用于储存最终的子序列长度
        for (int num : nums)
            //遍历 nums 数组中的每一个元素 num，将其作为键
        {
            cnt[num]++;
            //增加 cnt[num] 的计数。即统计每个数字在 nums 中出现的频率   
        }
        for (auto [key, val] : cnt)
        //遍历 cnt 中的每一个键值对，key 记录数组中的数字，val 是该数字出现的次数
        {
            if (cnt.count(key + 1))
            //判断 cnt 中是否存在键为 key + 1 的项。如果存在，说明 key 和 key + 1 的数字可以组成一个和谐子序列，因为它们之间的差值正好是 1
            {
                res = max(res, val + cnt[key + 1]);
                //如果存在 key + 1 ，则更新res，确保它的值是最长和谐子序列的长度
            }
        }
        return res;
        //返回 res，即数组 nums 中最长和谐子序列的长度
    }
};

5.示例演算：

输入：[1,3,2,2,5,2,3,7]

6.复杂度计算：

时间复杂度：需要遍历一次 nums 数组和哈希表中的每个元素，故时间复杂度为O(n)

空间复杂度：我们使用了一个哈希表来存储数组中每个不同元素的频次，最坏情况下哈希表的大小为n，故空间复杂度为O(n)

7.拓展：

双指针解法：

通过两个指针begin和end来找出数组中和谐序列的最大长度。

首先，数组排序，以便相同的元素聚集在一起。然后，初始化begin为0，res为0，表示和谐序列的最大长度。接下来，通过一个for循环遍历数组，end指针从头到尾逐一检查每个元素。在每次循环中，begin指针会向右移动，直到满足nums[end] - nums[begin] <= 1的条件，这样保证了当前窗口内的最大值和最小值之差不超过1。若nums[end] - nums[begin] == 1，则计算当前窗口的长度end - begin + 1，并更新res为最大值。最终返回最大和谐序列的长度res。通过这种方式，代码高效地查找和更新符合条件的最长和谐子序列的长度。

class Solution {
public:
    int findLHS(vector<int>& nums) {
        sort(nums.begin(), nums.end());  // 排序预处理，使相邻元素更容易比较
        int begin = 0;  // 定义滑动窗口的左指针，初始化为数组的第一个元素
        int res = 0;    // 初始化最大和谐序列的长度为0
        
        for (int end = 0; end < nums.size(); end++) {  // 右指针从头到尾遍历整个数组
            // 当窗口中最大值与最小值的差大于1时，缩小窗口
            while (nums[end] - nums[begin] > 1) {
                begin++;  // 左指针右移，缩小窗口，直到满足条件
            }
            // 如果当前窗口中的最大值与最小值的差正好为1，说明找到了一个和谐序列
            if (nums[end] - nums[begin] == 1) {
                res = max(res, end - begin + 1);  // 更新和谐序列的最大长度
            }
        }
        return res;  // 返回找到的最大和谐序列的长度
    }
};

双指针解法的空间效率更高，而哈希表解法的时间效率更高。