LC 128. Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int ans = 0;
        unordered_map<int, int> Map;
        for (auto &x: nums) {
            if (Map.count(x)) continue;
            auto left = Map.find(x - 1);
            auto right = Map.find(x + 1);

            int l = left != Map.end() ? left->second : 0;
            int r = right != Map.end() ? right->second : 0;

            int t = l + r + 1;
            Map[x] = Map[x - l] = Map[x + r] = t;
            ans = max(ans, t);
        }
        return ans;
    }
};

Time Complexity: O(n)
Space: O(n)

不停的往左右兩邊擴展就可以了