[LeetCode] 128. Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/

Longest Consecutive Sequence - LeetCode

Longest Consecutive Sequence - Medium

 

배열이 주어졌을때, 연속으로 증가하는 배열의 최대 길이를 묻는 문제다.

O(n)으로 풀이를 해야한다.

sort를 쓰는순간부터 O(n*log n)이 되어 초과된다.

 

풀이는 Hash를 이용하는 방법이다.

c++은 set이 아닌 unordered_set 을 반드시 이용하자

hash set에 배열을 넣고, 배열에서 하나씩 뽑아 1씩 증가시키며 hash set에 있는지 찾고, 있다면 count++을 하고 hash set에서 제거해준다. 1씩 감소도 마찬가지로 진행한다.

마지막으로 count의 최대값을 구해주자.

 

전체 풀이 코드

 

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s;
        int M=0,c,f;
        for (int n:nums) s.insert(n);
        for (int n:nums) {
            if (s.find(n)!=s.end()) {
                c=1;
                f = n-1;
                while (s.find(f)!=s.end()) c++,s.erase(f--);
                f = n+1;
                while (s.find(f)!=s.end()) c++,s.erase(f++);
            }
            M = max(M,c);
        }
        return M;
    }
};