Leetcode - 128. Longest Consecutive Sequence

문제

정렬되지 않은 integer배열 값중에 가장 긴 연속된 수 갯수는? (O(n)에 해결하라)

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.

해결 O(n)

hashtable에 값을 저장하고 table을 순회하면서 연속된 수들을 찾음. 아래 순회 방식을 주석과 함께 잘 살펴보기. 가지치기가 필요.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> table;
        int max_cnt = 0;
        
        for (auto it: nums)
            table[it] = 1;
        
        for (auto it: table) {
            int cur = it.first;
            /* if prev value is exist in table, there is no need to proceed 
               because in that case this cur value already has been checked. */
            if (table.find(cur - 1) != table.end())
                continue;
            
            /* check continuous from cur to */
            int cnt = 1;
            while (table.find(cur + 1) != table.end()) {
                cnt++;
                cur++;
            }
            max_cnt = max(max_cnt, cnt);
        }
        return max_cnt;
    }
};