C++ One Pass with Hash Table


  • 2
    G

    The idea is that if current element's min(element-1) / max(element+1) exist before which imply there is a harmonious subsequence, we could calculate the length of the subsequence by simply adding freq. of min/max and current element.

    public:
        int findLHS(vector<int>& nums) {
            
            unordered_map<int, int> map;
            auto max = 0;
            
            for(auto element : nums){
                
                map[element]++;
                if (map.count(element-1) > 0) {
                    max = std::max(max, map[element-1] + map[element] );
                }
                if (map.count(element+1) > 0) {
                    max = std::max(max, map[element+1] + map[element] );
                }
            }
            return max;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.