[ArraysHasing][Medium] 128. Longest Consecutive Sequence

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

 

주어진 숫자 배열에서 연속된 증가수의 최대 길이를 찾아라. 

이때 O(n)의 TC를 만족하는 알고리즘을 작성하라.

 

값에 대한 조회가 O(1)에 가능해야 하므로, hash를 사용해야 한다. 

또한 전체적으로 O(N)에 로직이 작성되어야 한다. 따라서 2중 for loop를 피한다. 

 

증가되는 수의 시작 지점을 조회하여 연속된 만큼 카운팅 한다. 

시작지점 조회 - O(n)

각 지점에 대한 연속된 수 카운팅 O(x) 

최적 O(n)

최악 O(n + x) 

 

음 다소 애매. 

int longestConsecutive(vector<int>& nums) 
{
    if(nums.size() <= 1)
        return nums.size();

    unordered_set<int> sBuff;
    for (auto k = 0; k < nums.size(); ++k)
    {
        if (sBuff.find(nums[k]) == sBuff.end())
            sBuff.insert(nums[k]);
    }

    int maxLen = 1;
    for (auto q = 0; q < nums.size(); ++q)
    {
        int dec = nums[q] - 1;
        int inc = nums[q] + 1;
        if (sBuff.find(dec)==sBuff.end() && sBuff.find(inc)!=sBuff.end())
        {
            // cout << nums[q] << endl;
            int cnt = 1;
            for (auto j = inc; ; ++j)
            {
                if (sBuff.find(j) != sBuff.end())
                    ++cnt;
                else
                {
                    maxLen = max(maxLen, cnt);
                    break;
                }
            }
        }
    }
    return maxLen;
}

 

결과도 애매.