longest-harmonious-subsequence

Longest Harmonious Subsequence – LeetCode 594

Problem

Description

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.

Answer

Original

Code

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int,int> m;
        for (int &i : nums) 
            ++m[i];
        int Max = 0;
        for (auto &i : m){
            if(m.count(i.first + 1))
                Max = max(Max, i.second + m[i.first + 1]);
        }
        return MaxF;
    }
};

思路

寻找要求的子串长，直接用map打表记录出现次数就行了。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$56$ ms，排名$9.96\%$

Better

思路

官方还给出了排序的做法。时间复杂度$O(nlog(n))$，空间复杂度$O(1)$。