128. Longest Consecutive Sequence

題目網址：https://leetcode.cn/problems/longest-consecutive-sequence/

題意：給一未排序的 array nums, 找出數字連續的最長 sequence（sequence 元素不需在 nums 中位置連續）。

注意：請設計 $O(n)$ time 的演算法

Solution：

想法：將 nums 視覺化發現, 每個 sequence 形成的首要條件就是開頭的數左邊沒有數, 結尾的數右邊沒有數

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_set<int> s(nums.begin(), nums.end());

        for (const auto& num : nums) {
            // 判斷左邊的數有無在 hash table 中
            if (s.find(num - 1) == s.end()) {
                int end = num + 1; // 則 num 可當作 sequence 的開頭
                while (s.find(end) != s.end()) {
                    end++;
                }
                res = max(res, end - num); // 檢查是否為最長 sequence
            }
        }
        return res;
    }
};

• time：$O(n)$ ➔ 雖然有 for loop 和 while loop, 但是每一個數最多被訪問 `2`` 次
  • 一次是 for (const auto& num : nums)
  • 一次是 if (s.find(num - 1) == s.end()), 也就是剛好是某數的左邊
• space：$O(n)$ ➔ s