<Data Structures/Algorithms> leetcode hot100 - 128.Longest Consecutive Sequence

[LeetCode Hot 100] 128. Longest Consecutive Sequence

Problem Link

When facing this problem, first think about how a human would approach it. Typically, we would see a number and check the whole sequence for consecutive numbers. If there are, we continue checking, picking numbers one by one to calculate the length, right?

To simplify, we don’t need to start from every number; we only need to start from the beginning of a consecutive sequence.

1. First, traverse the array and insert elements into a set. This removes duplicates and makes lookups convenient.
2. Traverse the set. For each element e, if e-1 exists in the set, skip it because e is not the start of a consecutive sequence.
3. If e-1 does not exist in the set, then e is the start of a consecutive sequence. Start checking e+1, e+2, ..., e+n until e+n does not exist. The length of the sequence is n.
4. After traversing the whole set, the maximum sequence length is the answer.

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;
    }
};

中文原文

[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;
    }
};