?????? 歡迎來到我的博客。希望您能在這里找到既有價值又有趣的內容，和我一起探索、學習和成長。歡迎評論區暢所欲言、享受知識的樂趣！
推薦：數據分析螺絲釘的首頁 格物致知 終身學習 期待您的關注
導航：
- LeetCode解鎖1000題: 打怪升級之旅：每題都包括3-5種算法，以及詳細的代碼實現，刷題面試跳槽必備
- 漫畫版算法詳解：通過漫畫的形式和動態GIF圖片把復雜的算法每一步進行詳細可視解讀，看一遍就掌握
- python源碼解讀：解讀python的源代碼與調用關系，快速提升代碼質量
- python數據分析可視化：企業實戰案例：企業級數據分析案例與可視化，提升數據分析思維和可視化能力
- 程序員必備的數學知識與應用：全面詳細的介紹了工程師都必備的數學知識
期待與您一起探索技術、持續學習、一步步打怪升級 歡迎訂閱本專欄????
題目描述
給定一個未排序的整數數組 nums，找出數字連續的最長序列的長度。要求時間復雜度在 O(n) 內。
注意：
- 這個序列不需要在原數組中是連續的。
示例：
輸入: [100, 4, 200, 1, 3, 2]
輸出: 4
解釋: 最長連續序列是 [1, 2, 3, 4]。它的長度是 4。
方法一：哈希表
解題步驟
- 使用哈希表存儲所有數字，以便快速查找數組中的任意數字是否存在。
- 遍歷數組
nums，對每個元素進行檢查：- 如果其前一個元素
(num - 1)不在哈希表中，則這是一個新序列的起點。
- 如果其前一個元素
- 從起點開始，遞增查找連續的數字，同時更新最長連續序列的長度。
- 返回找到的最大長度。
Python 示例
def longestConsecutive(nums):num_set = set(nums)max_length = 0for num in num_set:if num - 1 not in num_set:current_num = numcurrent_length = 1while current_num + 1 in num_set:current_num += 1current_length += 1max_length = max(max_length, current_length)return max_length# 示例使用
nums = [100, 4, 200, 1, 3, 2]
print(longestConsecutive(nums)) # 輸出: 4
算法分析
- 時間復雜度：O(n)。盡管看起來有雙層循環，但每個數字在內層循環中只訪問一次。
- 空間復雜度：O(n)，因為需要存儲數組元素的哈希表。
詳細步驟說明
-
構建哈希表：
- 將所有數字插入哈希表，確保每個數字能被快速查找。
- 例如，對于輸入
[100, 4, 200, 1, 3, 2]，哈希表為{100, 4, 200, 1, 3, 2}。
-
查找序列起點：
- 遍歷哈希表中的每個數字，判斷是否為序列的起點。
- 一個數字是序列起點的條件是其前一個數字不在哈希表中。
- 例如，
1是起點，因為0不在哈希表中。
-
構建序列：
- 從序列起點開始，逐步查找下一個連續數字，并計算序列長度。
- 例如，從
1開始，可以找到2、3和4，最終序列長度為4。
更多示例
-
輸入：
[0, -1, 1, 2, 3]- 輸出：
5 - 解釋：最長連續序列是
[-1, 0, 1, 2, 3]，長度為5。
- 輸出：
-
輸入：
[10, 5, 12, 3, 55, 6, 11, 8, 7, 9]- 輸出：
6 - 解釋：最長連續序列是
[5, 6, 7, 8, 9, 10]，長度為6。
- 輸出：
圖示與說明
考慮 nums = [100, 4, 200, 1, 3, 2]：
-
構建哈希表：
- 哈希表：
{100, 4, 200, 1, 3, 2}
- 哈希表：
-
查找序列起點：
初始數組: [100, 4, 200, 1, 3, 2] 哈希表構建: {100, 4, 200, 1, 3, 2}從 '1' 開始，因為 '0' 不在集合中，序列可以從 '1' 開始向上構建: 1 -> 2 -> 3 -> 4 連續序列長度為 4，是此數組的最長連續序列。 -
詳細步驟說明：
| 步驟 | 當前數字 | 當前序列 | 最長序列長度 |
|---|---|---|---|
| 初始 | [100, 4, 200, 1, 3, 2] | ||
| 構建哈希表 | {100, 4, 200, 1, 3, 2} | ||
| 步驟1 | 1 | [1] | 1 |
| 步驟2 | 1 -> 2 | [1, 2] | 2 |
| 步驟3 | 1 -> 2 -> 3 | [1, 2, 3] | 3 |
| 步驟4 | 1 -> 2 -> 3 -> 4 | [1, 2, 3, 4] | 4 |
🌹🌹如果覺得這篇文對你有幫助的話，記得一鍵三連關注、贊👍🏻、收藏是對作者最大的鼓勵，非常感謝 ?(^_-)
????作者知識有限，如有錯誤，請各位大佬評論區批評指正，不勝感激?(^_-)
2.9-2.10)
