LeetCode Longest Harmonious Subsequence We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1. Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences. Example 1:

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Note: The length of the input array will not exceed 20,000.

---

一个和谐的数组是该数组的最大值和最小值只相差1。给定一个数组，求该数组的和谐子序列的最大长度。 子序列问题，又有作差问题，开始还以为是用DP来解，想了半天没想出好的解法。 后来看了一下标签用hash来做，恍然大悟。 仔细理解一下这个和谐数组的定义，最大数和最小数只相差1，说明这个子序列肯定只有两个不同的数，而且这两个数只相差1。 这就好办了，我们用hash表统计一下数组中每个数出现的频率，然后对于每个不同的数，看看该数相邻的数是否在hash表中，如果在的话，从数组中提取出这两个相邻的数的所有出现，构成的子序列就是一个和谐子序列。不断更新和谐子序列的最大长度。注意，假如考虑3构成的和谐子序列，则另一个数可能是2或者4，但是如果2在原数组中的话，已经考虑2和3构成和谐子序列的情况了，所以对于每个数，我们统一只考虑比它大1的数即可。 完整代码如下： [cpp] class Solution { public: int findLHS(vector<int>& nums) { unordered_map<int, int> hash; for (const auto &i : nums)++hash[i]; int ans = 0; for (const auto &it : hash) { if (hash.find(it.first + 1) != hash.end()) { ans = max(it.second + hash[it.first + 1], ans); } } return ans; } }; [/cpp] 本代码提交AC，用时102MS。]]>