Li Kou daily question - day 30 -594 Longest harmonic subsequence

2022.6.28 Did you brush the questions today ？

---

subject ：

A harmonious array is the difference between the maximum and minimum values of elements in an array Is precisely 1 .

Now? , Give you an array of integers nums , Please find the length of the longest harmonious subsequence among all possible subsequences .

A subsequence of an array is a sequence derived from an array , It can be done by deleting some elements or not deleting elements 、 Without changing the order of the other elements .

analysis ：

Give you an array , Find the inside that can form ,|x-y|=1 When the conditions ,x and y The maximum number of elements added up .

Ideas ： We put each number in a hash table . Then judge whether the key values in the hash table have a difference of 1 Of , If there is , Then find the key value pairs corresponding to the two key values , Then find the largest sum .

analysis ：

1. Hashtable

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> cnt;
        int res = 0;
        for (int num : nums) {
            cnt[num]++;
        }
        for (auto it : cnt)
        {
            if (cnt.count(it.first + 1)) 
            {
                //it.second Current second
                //cnt[it.first + 1] The next one second
                res = max(res, it.second + cnt[it.first + 1]);
            }
        }
        return res;
    }
};

2. Double pointer

We can use two pointers , A number that points to a small number , A number that points to a large number , If the difference between two pointers is not 1, Then put the front , Back pointer keeps moving back , When the satisfaction difference is found, it is 1 when , Then record the subscript difference at this time , Then the back pointer continues to move back , Determine whether the next number meets the .

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