Sunday, September 22, 2019

594. Longest Harmonious Subsequence


Easy
We define a harmounious array as 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.


class Solution {
public:
    int findLHS(vector<int>& nums) {        
        unordered_map<int, int> valCount;//count for values 
        for(int val : nums)
        {
            valCount[val]++;
        }
        // calculate the value that around it
        int res = 0;
        for(auto pair : valCount)
        {
            int key = pair.first;
            // res = max(res, valCount[key] + valCount[key+1]); //would error
            if(valCount.find(key+1) !=valCount.end())
            {
                res = max(res, valCount[key]+ valCount[key+1]);
            }
        }
        return res;
    }
};

注意,这里会有个语法的奇怪现象:
// res = max(res, valCount[key] + valCount[key+1]); //would error

结果会跳出循环




No comments:

Post a Comment