【C++刷题】力扣-#594-最长和谐子序列
题目描述
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 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
解释:
不存在和谐子序列。
题解
- 统计每个数字的出现次数:使用哈希表 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[num]++;
numSet.insert(num);
}
int maxLength = 0;
// 遍历集合中的数字,找到最大值和最小值相差为1的两个值
for (int num : numSet) {
if (numSet.find(num + 1) != numSet.end()) {
// 计算子序列的长度
int length = countMap[num] + countMap[num + 1];
maxLength = max(maxLength, length);
}
}
return maxLength;
}
复杂度分析
● 时间复杂度:O(n),其中 n 是数组 nums 的长度。我们需要遍历一次数组来构建哈希表和集合,然后遍历集合中的每个元素来计算子序列的长度。
● 空间复杂度:O(n),用于存储哈希表和集合。
这个算法的优势在于它直接使用哈希表来统计数字的出现次数,并通过一次遍历来找到最长和谐子序列的长度。这种方法简单且高效,适用于处理大数据集。