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; // 返回找到的最大和諧序列的長度}
};
雙指針解法的空間效率更高，而哈希表解法的時間效率更高。
