算法-每日一题（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;//创建哈希表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;  // 返回找到的最大和谐序列的长度}
};

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