Leetcode[Hash] Longest Consecutive Sequence 풀어보기

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

Longest Consecutive Sequence - LeetCode

 

연속된 수열을 찾는 문제입니다.

다만 복잡도가 O(n)으로서 동작해야합니다.

 

만약에 정렬되어있었다면 그대로 훑어가면서 확인하면 되었겠지만 순서자체가 랜덤으로 섞여있어서 불가능합니다.

그리고 sort자체는 보통 O(NlogN)이기 때문에 사용해서 훑는 것도 불가능합니다. 따라서 Hash를 사용해 찾는 unordered_set을 이용했습니다.

 

연속된 값을 찾기 위해서 만약의 set의 element x를 순회할 때 x-1이 존재하지 않는다면 해당 sequence의 시작점이 될것이고 아니라면 이미 앞에 무엇이 있기 때문에 해당 숫자에 대해 탐색할 필요가 없을 것입니다. 

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int ans = 0;
        for (int x : s)
        {
            if (s.find(x - 1) == s.end())
            {
                int current = x;
                int length = 1;

                while (s.find(current + 1) != s.end())
                {
                    ++current;
                    ++length;
                }
                ans = max(ans, length);
            }
        }
    }
};