문제를 본 날: 2022년 11월 11일 오전 2:00 (GMT+9)

문제를 푼 날: 2022년 11월 12일 오전 10:35 (GMT+9)

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

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is[1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

• 0 <= nums.length <= 105
• 109 <= nums[i] <= 109

Solution

class Solution {
private:
    unordered_map<int, int> table;
    vector<int> visited;
    int ans;
    
public:
    
    void dfs(int cur, int& acc){
        const auto pos = table.find(cur);
        if(pos == table.end()){
            return;
        }
        
        else if(visited[pos->second]){
            return;
        }
        
        visited[pos->second] = 1;
        ans = max(ans, ++acc);
        
        
        dfs(cur+1, acc);
        dfs(cur-1, acc);
    }
    
    int longestConsecutive(vector<int>& nums) {
        const int n = nums.size();
        visited = vector<int>(n, 0);
        
        for(int i=0;i<n;++i){
            table[nums[i]] = i;
        }
        
        for(int i=0;i<n;++i){
            if(!visited[i]){
                int acc = 0;
                dfs(nums[i], acc);
            }
        }
        
        return ans;
    }
};