<数据结构/算法> leetcode hot100系列. 128.最长连续序列

[LeetCode hot 100] 128. 最长连续序列

题目链接

遇到这种题，首先想一想，作为一个人类，我们怎么思考这个问题。我们肯定是每看到一个数就去整个序列里面找有没有挨着的，如果有，那就顺着继续找，最后一个数一个数地摘出来，算一个长度对吗？

简化这个过程，我们不需要每个数都找，而是只需要从一个连续序列开头的那个数往后找就行。

1. 首先先遍历一下这个数组，并且放入集合中，一来是去重，二来是方便后面的查找。
2. 遍历这个集合，对于每个元素e，如果集合中存在比它小1的元素e-1，那就先不管这个数，因为肯定不是一个连续序列的开头。
3. 如果集合中不存在e-1，就说明e一定是一个连续序列的开头，那么就开始找e+1, e+2, …, e+n，直到e+n找不到了，说明序列到此结束，当前序列的长度就是n。
4. 最后遍历完之后输出序列长度的最大值就行。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        set<int> numSet;
        for(auto& num : nums){
            numSet.emplace(num);
        }
        int maxLength = 0;
        for(auto& num : numSet){
            if(numSet.count(num-1))
                continue;
            int len = 0;
            while(numSet.count(num+len)){
                len++;
            }
            maxLength = max(maxLength, len);
        }
        return maxLength;
    }
};