594. 最长和谐子序列

594. 最长和谐子序列

排序后滑动窗口

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

O(NlogN)

哈希表，把x和x+1的出现个数加上去，厉害啊

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> map;
        int ret;
        for(auto num : nums)
            ++map[num];
        for(auto [num, time] : map)
            if(map.count(num + 1))
                ret = max(ret, time + map[num + 1]);
        return ret;
    }
};