594: Longest-Harmonious-Subsequence
Easy

table of contents

Even if we were to use a hash-map, since we want to iterate through all the keys in order, that implies that we will still have to sort nums.

Therefore, we should just sort nums first, and then simply run a two-pointers solution, with:

Then if nums[l] + 1 == nums[r], then we can update our ans if r-l+1 is larger.

code

class Solution {
public:
    int findLHS(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        int curr = nums[0];
        int l = 0, r = 0, ans = 0;
        while (r < nums.size()-1) 
        {
            if(nums[r+1] > nums[l] + 1)
            {
                if (nums[r] == nums[l]+1) 
                {
                    ans = max(r-l+1, ans);
                }
                while(l <= r && nums[l] != nums[r]) 
                {
                    ++l;
                }
            }
            ++r;
        }
        if (nums[r] == nums[l]+1) 
        {
            ans = max(r-l+1, ans);
        }
        return ans;
    }
};

complexity