1 題目描述

給一個數組，求連續的數字最多有多少個，這邊特特書挑站是 時間複雜度要求是 O(n)。

2 解法

2.1 我的解法

一開始想說把 nums 放進去 Set 裡面，他是會有一個順序的，但並不會從小排到大，所以後來才硬是把他排序過後再比較。
使用 set 的好處是可以把重複的數字過濾掉，這樣就不用擔心重複的數字會影響到我們的計算。

大概是這樣的感覺：

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums_sets: Set[int] = set(nums)     # 不重複的數字集合 當作字典查找
        sorted_nums = sorted(nums_sets)     # 排序後並filter掉重複的 按照順序 pop
        max_len = 0     # 最大len
        cur_len = 1     # 目前len
        while nums_sets:     # 只要 sorted_num 還有值就繼續比較
            tar = sorted_nums.pop() + 1
            if {tar}.issubset(nums_sets):   # 是否存在 pop() + 1 的值在字典
                cur_len += 1                # 若是存在，長度 + 1
            else:
                cur_len = 1 # 沒有 並且 已經斷掉 就換下一個重新開始
            max_len = max(max_len, cur_len)
        return max_len

時間複雜度O(nlogn)

建立 nums_sets 集合的時間複雜度是 O(n)。
排序 nums_sets 集合的時間複雜度是 O(nlogn)。
進行 while 循環的時間複雜度是 O(n)。
因此總的時間複雜度是 O(nlogn)。

空間複雜度O(n)

建立 nums_sets 集合的空間複雜度是 O(n)。
排序 nums_sets 集合的空間複雜度是 O(n)。
因此總的時間複雜度是 O(n)。

但是這個做法最大的問題是 sorted 的時間複雜度是 O(nlogn)，所以這個解法是不合格的。

2.2 改良

上面的做法最大的問題是，需要排序，為什麼要排序的原因是，這樣就可以專心地往一個方向找，但是這樣的時間複雜度是 O(nlogn) 是不符合題目要求的。
如果我們不排序，那就變成左右兩個方向都要同時找，慢慢擴大範圍，我們不確定抓的第一個數字是否在 nums 中為最小，假設他是中間的數值好了，我們就要往左右兩邊找，看看可以找到多少連續的數字。在找的時候，我們可以把找過的數字從 nums_sets 中刪除，這樣當發生斷掉的狀況時，可以從剩下的 nums_sets 隨便挑一個，繼續開始往左右兩邊找。

實際帶入數字大概是這樣的感覺：

class Solution:
    def longestConsecutive2(self, nums: List[int]) -> int:
        if not nums:
            return 0

        nums_set: Set[int] = set(nums)
        max_len = 0

        while nums_set:
            cur = nums_set.pop() # 如果左邊跟右邊都無法擴展時，就該重新開始 pop() 出來的數值一定沒當過 target 
            left = cur - 1
            right = cur + 1
            cur_len = 1

            # 一直往左邊找直到找不到
            while left in nums_set:
                nums_set.remove(left)
                left -= 1
                cur_len += 1

            # 一直往右邊找直到找不到
            while right in nums_set:
                nums_set.remove(right)
                right += 1
                cur_len += 1

            max_len = max(max_len, cur_len)

        return max_len