LeetCode 128 Longest Consecutive Sequence

    
        标签：
        
            数组问题
        
            LeetCode
        
    发布于：2022-02-18 23:18:57
    编辑于：2022-02-19 10:25:16
    浏览量：606

概述

https://leetcode.com/problems/longest-consecutive-sequence/

要求 O(n) 时间复杂度。

直接法

假设最长序列为从 i 到 j，不排序的话，我们要怎么记录从 i 到 j 是连续的呢？

目前一个想法是，从头遍历数组，维护一组连续列表，每遇到一个值，就判断是否之前存在可以加上去的列表。

那要怎么 O(n) 时间复杂度下完成列表的更新呢？其只能是 O(1)。

我们为维护两个哈希表中的项，一个 key 为每个列表的起始值，一个 key 为列表的结束值，value 就存列表的长度。

~~遍历一遍后，我们需要再遍历一遍列表，看看有没有能够合并的。~~

注意防范重复值，再加个 map 就好了。

62 / 70 test cases passed：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> start;
        unordered_map<int, int> end;
        unordered_map<int, bool> visited;
        int ans = 0;
        for (auto n : nums) {
            if (visited[n]) continue;
            visited[n] = true;
            if (start[n+1] != 0 && end[n-1] != 0) {
                int newNum = start[n+1] + end[n-1] + 1;
                ans = max(newNum, ans);
                start[n-end[n-1]] = ans;
                end[n+start[n+1]] = ans;
                start.erase(n+1);
                end.erase(n-1);
            } else if (start[n+1] != 0) {
                start[n] = start[n+1] + 1;
                end[n+start[n+1]] ++;
                start.erase(n+1);
                ans = max(ans, start[n]);
            } else if (end[n-1] != 0) {
                end[n] = end[n-1] + 1;
                start[n-end[n-1]] ++;
                end.erase(n-1);
                ans = max(ans, end[n]);
            } else {
                start[n] = 1;
                end[n] = 1;
                ans = max(ans, 1);
            }
        }

        return ans;
    }
};

没找到 bug 在哪，不浪费时间了。

只从 streak 的开始处开始检查

https://leetcode.com/problems/longest-consecutive-sequence/discuss/41057/Simple-O(n)-with-Explanation-Just-walk-each-streak

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int ans = 0;
        for (auto n : nums) {
            if (s.count(n-1) == 0) {  // only start from the start of a streak
                int y = n;
                while (s.count(y)) y ++;
                ans = max(ans, y - n);
            }
        }
        return ans;
    }
};

Links: leetcode-128-longest-consecutive-sequence