128. Longest Consecutive Sequence.md

128. 最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

// 最坏需要遍历三遍数组, O(n)
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_set<int> us(nums.begin(), nums.end());
        for (int num : nums) {
            if (us.count(num - 1) == 0) {  // 如果num是连续序列的左端
                int count = 1;
                while (us.count(++num)) ++count;
                res = max(res, count);
            }
        }
        return res;
    }
};

2020/07/05 00:26