2021年04月11日 周日 天气阴 【不悲叹过去，不荒废现在，不惧怕未来】

本文目录

• 1. 题目简介
• 2. 判断左边界法
• 参考文献

---

1. 题目简介

128. 最长连续序列

2. 判断左边界法

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_set<int> uset;
        // 第一步：去重
        for(const int &num:nums) 
            uset.insert(num);
        // 第二步：对数组中的每个元素依次进行判断
        // 不是左边界就直接跳过，是左边界就循环找到最长连续序列
        for(int i=0;i<nums.size();++i){
            if(uset.find(nums[i]-1) != uset.end()) 
                continue;
            int j = 0;
            while(uset.find(nums[i]+j) != uset.end()) 
                ++j;
            res = max(res, j);
        }
        return res;
    }
};

每个元素最多遍历两次（内循环一次，外循环一次），所以时间复杂度为 O(n) 。

---

参考文献

https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/jian-ming-yi-dong-de-javajie-da-by-lan-s-pf26/