算法-每日一题（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] <= 1093.解题思路：
我们可以通过哈希表的方式，利用元素频率统计来求解数组中的最长和谐子序列。首先，创建一个哈希表 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;//创建哈希表cntint 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]
| 执行步骤 | cnt 内容 | 当前 key | 检查 key+1 | 计算长度 | res 更新 |
|---|---|---|---|---|---|
| 初始化后 | {} | - | - | - | 0 |
| 处理元素 ` | |||||
| 1` | {1:1} | - | - | - | 0 |
| 处理元素 ` | |||||
| 3` | {1:1, 3:1} | - | - | - | 0 |
| 处理元素 ` | |||||
| 2` | {1:1, 2:1, 3:1} | - | - | - | 0 |
| 处理元素 ` | |||||
| 2` | {1:1, 2:2, 3:1} | - | - | - | 0 |
| 处理元素 ` | |||||
| 5` | {1:1, 2:2, 3:1, 5:1} | - | - | - | 0 |
| 处理元素 ` | |||||
| 2` | {1:1, 2:3, 3:1, 5:1} | - | - | - | 0 |
| 处理元素 ` | |||||
| 3` | {1:1, 2:3, 3:2, 5:1} | - | - | - | 0 |
| 处理元素 ` | |||||
| 7` | {1:1, 2:3, 3:2, 5:1, 7:1} | - | - | - | 0 |
遍历 key=1 | 不变 | 1 | 存在 (key=2) | 1+3=4 | 4 |
遍历 key=2 | 不变 | 2 | 存在 (key=3) | 3+2=5 | 5 |
遍历 key=3 | 不变 | 3 | 不存在 (key=4) | - | 5 |
遍历 key=5 | 不变 | 5 | 不存在 (key=6) | - | 5 |
遍历 key=7 | 不变 | 7 | 不存在 (key=8) | - | 5 |
| 最终结果 | 5 |
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; // 初始化最大和谐序列的长度为0for (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; // 返回找到的最大和谐序列的长度}
};
双指针解法的空间效率更高，而哈希表解法的时间效率更高。