題目

????????給定一個未排序的整數數組 nums ，找出數字連續的最長序列（不要求序列元素在原數組中連續）的長度。請你設計并實現時間復雜度為 O(n) 的算法解決此問題。

????????示例 1：

輸入：nums = [100,4,200,1,3,2]
輸出：4
解釋：最長數字連續序列是 [1, 2, 3, 4]。它的長度為 4。

????????示例 2：

輸入：nums = [0,3,7,2,5,8,4,6,0,1]
輸出：9

排序法

????????排序法在最壞情況下的時間復雜度為O(nlogn)，不滿足本題時間復雜度為O(n)的要求。但它提供了一個不同的解題視角，還是值得我們學習一下的。使用排序法求解本題的主要步驟如下。

????????1、首先，將輸入數組nums進行排序。這一步的目的是使得連續的數字相鄰，便于后續遍歷查找連續序列。

????????2、對排序后的數組進行遍歷，并初始化兩個變量。其中，current_streak用于記錄當前連續序列的長度，longest_streak用于記錄遇到的最長連續序列的長度。

????????3、在遍歷過程中，比較當前元素與前一個元素的關系。如果當前元素正好比前一個元素大1，則說明它們屬于同一個連續序列，此時current_streak加1。否則，說明遇到了新的序列起點，此時更新longest_streak（如果current_streak大于longest_streak），并將current_streak重置為1。

????????注意：需要對數組中存在相同元素的情況進行額外處理，以避免重復元素導致的誤判。

????????根據上面的算法步驟，我們可以得出下面的示例代碼。

def get_longest_consecutive_by_sort(nums):if not nums:return 0nums.sort()longest_streak = 1current_streak = 1for i in range(1, len(nums)):# 避免重復元素導致的誤判if nums[i] != nums[i-1]:if nums[i] == nums[i-1] + 1:current_streak += 1else:longest_streak = max(longest_streak, current_streak)current_streak = 1return max(longest_streak, current_streak)print(get_longest_consecutive_by_sort([100, 4, 200, 1, 3, 2]))
print(get_longest_consecutive_by_sort([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))

哈希法

????????使用哈希法的基本思想如下：首先，將所有數組中的元素添加到哈希集合中，以便快速查詢一個數字是否已存在。然后，遍歷數組中的每個元素，對于每個元素，檢查它是否是某個連續序列的起始點（即檢查num - 1不在哈希集合中）。如果是起始點，則嘗試向后擴展序列，同時更新最長序列長度。為了避免重復計算，每當我們確定了一個數字屬于某個連續序列時，就將其從哈希集合中移除。使用哈希法求解本題的主要步驟如下。

????????1、初始化。創建一個空的哈希集合num_set，用來存儲數組中的所有數字。

????????2、填充哈希集合。遍歷數組nums，將所有元素添加到哈希集合num_set中。

????????3、遍歷并檢查連續性。再次遍歷數組nums，對于每個元素，檢查它是否能作為連續序列的起點，即檢查 num - 1 是否不在 num_set 中。

????????4、擴展序列并更新長度。如果找到了一個起點，就嘗試通過不斷檢查 num + 1 是否在 num_set 中來擴展序列，并相應地更新最長序列長度。

????????5、移除已訪問元素。在擴展序列的過程中，將訪問過的數字從 num_set 中移除，以避免之后的重復計算。

????????6、返回找到的最長連續序列的長度。

????????根據上面的算法步驟，我們可以得出下面的示例代碼。

def get_longest_consecutive_by_hash(nums):if not nums:return 0num_set = set(nums)longest_streak = 0for num in num_set:if num - 1 not in num_set:current_num = numcurrent_streak = 1while current_num + 1 in num_set:current_num += 1current_streak += 1longest_streak = max(longest_streak, current_streak)return longest_streakprint(get_longest_consecutive_by_hash([100, 4, 200, 1, 3, 2]))
print(get_longest_consecutive_by_hash([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))

總結

????????使用哈希法求解本題時，每個元素僅被訪問兩次：一次加入哈希集合，另一次作為序列起點檢查。遍歷和序列擴展操作均在常數時間內完成，故總的時間復雜度為O(n)，滿足本題的要求。另外，哈希法需要額外的空間來存儲哈希集合。最壞情況下，數組中的所有元素都是唯一的，因此哈希集合將存儲n個元素，空間復雜度為O(n)。