LC128: Longest Consecutive Sequence

작성일

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

  • 연휴동안 100문제 풀기 (2/100)
  • 15분 47초
  • 이번에는 좀 쉬웠다. 다만 양쪽으로 퍼지는걸 처음부터 생각 못함.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty()) return 0;
        unordered_set<int> notVisited;
        for(int i = 0; i < nums.size(); i++)
            notVisited.insert(nums[i]);
        int ans = 1;
        for(int i = 0; i < nums.size(); i++) {
            int next = nums[i], candi = 0;
            while (notVisited.count(next)) {
                notVisited.erase(next);
                ++next, ++candi, ans = max(candi, ans);
            }
            next = nums[i]-1;
            while (notVisited.count(next)) {
                notVisited.erase(next);
                --next, ++candi, ans = max(candi, ans);
            }
        }
        return ans;
    }
};