题目描述

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

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

样例

输入: [1,3,2,2,5,2,3,7]
输出: 5
解释: 最长的和谐子序列是：[3,2,2,2,3]。

算法

(哈希表) $O(n)$

1. 使用 unordered_map 哈希表，记录原数组中每个数字出现的次数。
2. 遍历哈希表，对于每个数字 num，在哈希表中求 num + 1 数字出现的次数，二者相加即得到一个极大和谐子序列的长度。在所有的极大和谐子序列中取最大值即可。

时间复杂度

• 哈希表的插入和查询的时间复杂度都是 $O(1)$，故总时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int findLHS(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> hash;
        for (int i = 0; i < n; i++)
            hash[nums[i]]++;
        int ans = 0;
        for (auto num : hash) {
            unordered_map<int, int>::iterator it;
            it = hash.find(num.first + 1);
            if (it != hash.end())
                ans = max(ans, num.second + it -> second);
        }
        return ans;
    }
};