128-最长连续序列

LeetCode 128. Longest Consecutive Sequence

LeetCode-128

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.

method

从一个数n开始往后遍历，如果n+1存在就res++，注意：

• 如果n-1存在，就不用继续算了，肯定不会比从n-1开始算更长
• 如果n-1不存在，就以当前值为起点开始向后查找连续序列，每找到一个长度就加1

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> st;
    for (auto n : nums) st.insert(n);
    int res = 0;
    for (auto n : nums) {
        if (!st.count(n - 1)) {
            int curNum = n;
            int curLen = 1;
            while (st.count(curNum + 1)) {
                curNum += 1;
                curLen += 1;
            }
            res = max(res, curLen);
        }
    }
    return res;
}