力扣每日一题-第30天-594.最长和谐子序列

2022.6.28今天你刷题了吗？

---

题目：

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

分析：

给你一个数组，找到里面可以构成，|x-y|=1条件时，x和y加起来的元素数目最多。

思路：我们把每个数存进哈希表。然后判断哈希表中键值是否存在相差为1的，如果有，则把两个键值对应的键值对求出来，然后找到最大的和。

解析：

1.哈希表

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> cnt;
        int res = 0;
        for (int num : nums) {
            cnt[num]++;
        }
        for (auto it : cnt)
        {
            if (cnt.count(it.first + 1)) 
            {
                //it.second当前的second
                //cnt[it.first + 1]下一个的second
                res = max(res, it.second + cnt[it.first + 1]);
            }
        }
        return res;
    }
};

2.双指针

我们可以利用两个指针，一个指向小的数，一个指向大的数，如果两个指针之间相差不为1，则把前，后指针不断后移，当找到了满足差为1时，则记录此时的下标差，然后后指针继续后移，判断下一个数是否满足。

class Solution {
public:
    int findLHS(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int begin = 0;
        int end = 0;
        int res = 0;
        for (auto end = 0; end < nums.size(); end++)
        {
            while (nums[end] - nums[begin] > 1)
            {
                begin++;
            }
            if (nums[end] - nums[begin] == 1)
            {
                res = max(res, end - begin + 1);
            }
        }
        return res;
    }
};