594. 最長和諧子序列
和諧數(shù)組是指一個數(shù)組里元素的最大值和最小值之間的差別 正好是 1 斥难。
現(xiàn)在跟伏，給你一個整數(shù)數(shù)組 nums 泳桦，請你在所有可能的子序列中找到最長的和諧子序列的長度束倍。
數(shù)組的子序列是一個由數(shù)組派生出來的序列，它可以通過刪除一些元素或不刪除元素倔叼、且不改變其余元素的順序而得到肛度。
示例 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
方法二：哈希映射
在方法一中郑现，我們枚舉了 x 后夕春，遍歷數(shù)組找出所有的 x 和 x + 1未荒。我們也可以用一個哈希映射（HashMap）來存儲每個數(shù)出現(xiàn)的次數(shù)，這樣就能在 O(1)O(1) 的時間內(nèi)得到 x 和 x + 1 出現(xiàn)的次數(shù)及志。
我們首先遍歷一遍數(shù)組片排，得到哈希映射。隨后遍歷哈希映射速侈，設當前遍歷到的鍵值對為 (x, value)率寡，那么我們就查詢 x + 1 在哈希映射中對應的值，就得到了 x 和 x + 1 出現(xiàn)的次數(shù)倚搬。
方法三：哈希映射 + 單次掃描
在方法二中冶共，我們需要對數(shù)組進行一次掃描，再對哈希映射進行一次掃描每界。事實上比默，我們也可以設計出只進行一次掃描的算法。
我們掃描一次數(shù)組盆犁，當掃描到元素 x 時，我們首先將 x 加入哈希映射篡九，隨后獲取哈希映射中 x - 1, x, x + 1 三者出現(xiàn)的次數(shù) u, v, w谐岁，那么 u + v 即為 x - 1, x 組成的和諧子序列的長度，v + w 即為 x, x + 1 組成的和諧子序列的長度榛臼。假設數(shù)組中最長的和諧子序列的最后一個元素在數(shù)組中的位置為 i伊佃，那么在掃描到 nums[i] 時，u + v 和 v + w 中一定有一個就是答案沛善。因此這種方法可以找到最長的和諧子序列的長度航揉。
class Solution {
public:
int findLHS(vector<int>& nums) {
unordered_map<int, int> map;
int ans = 0;
for (int i : nums) {
map[i]++;
if(map.count(i - 1))
ans = max(ans, map[i] + map[i - 1]);
if(map.count(i + 1))
ans = max(ans, map[i] + map[i + 1]);
}
return ans;
}
};
