1.题目描述
和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。 现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。 示例 1: 说明: 输入的数组长度最大不超过20,000.
2.方法1（两次遍历）
对于当前枚举的元素 x，它可以和 x + 1 组成和谐子序列。用哈希表保存数组每个值出现的次数，再遍历一遍整个数组，找出等于 x 和 x + 1 的出现次数，并找出x和x + 1出现次数之和的最大值，最大值就是最长和谐子序列的长度。
3.代码
class Solution {
public:
int findLHS(vector
<int>& nums
) {
map
<int, int> hash_map
;
for(int i
= 0;i
< nums
.size(); ++i
){
++hash_map
[nums
[i
]];
}
int res
= 0;
for(auto iter
= hash_map
.begin(); iter
!= hash_map
.end(); ++iter
){
auto keyPlus1
= hash_map
.find(iter
->first
+ 1);
if(keyPlus1
!= hash_map
.end()){
res
= max(res
, iter
->second
+ keyPlus1
->second
);
}
}
return res
;
}
};
5.方法2（单次遍历）
扫描一次数组，当扫描到元素 x 时，首先将 x 加入哈希映射，随后获取哈希映射中 x - 1, x, x + 1 三者出现的次数 u, v, w，那么 u + v 即为 x - 1, x 组成的和谐子序列的长度，v + w 即为 x, x + 1 组成的和谐子序列的长度。假设数组中最长的和谐子序列的最后一个元素在数组中的位置为 i，那么在扫描到 nums[i] 时，u + v 和 v + w 中一定有一个就是答案。因此这种方法可以找到最长的和谐子序列的长度。
6.代码
class Solution {
public:
int findLHS(vector
<int>& nums
) {
map
<int, int> hash_map
;
int res
= 0;
for(int i
= 0;i
< nums
.size(); ++i
){
++hash_map
[nums
[i
]];
auto w
= hash_map
.find(nums
[i
] + 1);
auto u
= hash_map
.find(nums
[i
] - 1);
if(w
!= hash_map
.end()){
res
= max(res
, hash_map
[nums
[i
]] + hash_map
[nums
[i
]+1]);
}
if(u
!= hash_map
.end()){
res
= max(res
, hash_map
[nums
[i
]] + hash_map
[nums
[i
]-1]);
}
}
return res
;
}
};
4.复杂度分析
时间复杂度：O(n) 空间复杂度：O(n)
