594. Longest Harmonious Subsequence

https://leetcode.com/problems/longest-harmonious-subsequence/

Longest Harmonious Subsequence - LeetCode

난이도 : easy

 

문제

배열이 주어질 때, 최대값과 최소값이 정확히 1차이가 나는 subsequence들의 최대 길이를 구해라.

 

 입력으로 들어오는 원소의 갯수가 2 * 10^4 O(N^2) 으로 풀수 있어 보인다. 일단은 오늘은 unorded_map 을 사용해보려고 한다.  unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)이다.

 해당 문제는 반복문을 수행하면서 unordered_map 에 숫자를 기록합니다. 그리고 unordered_map에서 key - 1 또는 key + 1인지 찾아 unordered_map에 있는 경우 결과를 업데이트 한다.

 

class Solution {
public:
    int findLHS(vector<int>& nums) {
        
        unordered_map<int, int> m;
        
        int res = 0;
        for (auto i: nums) {
            m[i]++;
            if(m.count(i + 1))
                res = max(res, m[i] + m[i + 1]);
            if(m.count(i - 1))
                res = max(res, m[i] + m[i - 1]);
        }

        return res;        
    }
};