【C++刷题】力扣-#594-最长调和子序列
题目形貌调和数组是指一个数组里元素的最大值和最小值之间的差异 恰好是 1 。
给你一个整数数组 nums ，请你在全部大概的子序列中找到最长的调和子序列的长度。 数组的 子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变别的元素的顺序而得到。
示例
示例 1
输入：nums =
输出：5
解释：
最长和谐子序列是 。
示例 2
输入：nums =
输出：2
解释：
最长和谐子序列是 ， 和 ，长度都为 2。
示例 3
输入：nums =
输出：0
解释：
不存在和谐子序列。
题解
[*]统计每个数字的出现次数：使用哈希表 countMap 来统计 nums 中每个数字的出现次数。
[*]寻找调和子序列：遍历哈希表中的每个数字，对于每个数字 num，查抄 num + 1 是否也存在于哈希表中。如果存在，则说明找到了一个长度至少为2的调和子序列。将这两个数字的出现次数相加，得到这个子序列的长度，并更新最长调和子序列的长度。
[*]返回结果：返回盘算出的最长调和子序列的长度。
代码实现
int findLHS(vector<int>& nums) {
unordered_map<int, int> countMap;
unordered_set<int> numSet;
// 统计每个数字的出现次数并存储在集合中
for (int num : nums) {
countMap++;
numSet.insert(num);
}
int maxLength = 0;
// 遍历集合中的数字，找到最大值和最小值相差为1的两个值
for (int num : numSet) {
if (numSet.find(num + 1) != numSet.end()) {
// 计算子序列的长度
int length = countMap + countMap;
maxLength = max(maxLength, length);
}
}
return maxLength;
}
复杂度分析
● 时间复杂度：O(n)，此中 n 是数组 nums 的长度。我们需要遍历一次数组来构建哈希表和聚集，然后遍历聚集中的每个元向来盘算子序列的长度。
● 空间复杂度：O(n)，用于存储哈希表和聚集。
这个算法的上风在于它直接使用哈希表来统计数字的出现次数，并通过一次遍向来找到最长调和子序列的长度。这种方法简朴且高效，适用于处理大数据集。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]