【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
解释：
不存在和谐子序列。

题解

1. 统计每个数字的出现次数：使用哈希表 countMap 来统计 nums 中每个数字的出现次数。
2. 寻找和谐子序列：遍历哈希表中的每个数字，对于每个数字 num，检查 num + 1 是否也存在于哈希表中。如果存在，则说明找到了一个长度至少为2的和谐子序列。将这两个数字的出现次数相加，得到这个子序列的长度，并更新最长和谐子序列的长度。
3. 返回结果：返回计算出的最长和谐子序列的长度。

代码实现

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)，用于存储哈希表和集合。
这个算法的优势在于它直接使用哈希表来统计数字的出现次数，并通过一次遍历来找到最长和谐子序列的长度。这种方法简单且高效，适用于处理大数据集。