“最長連續序列”是一道極具代表性的數組處理問題， 本文將帶你從直觀思路出發，逐步推導出最優解法，并通過場景化記憶技巧掌握核心邏輯。
一、題目描述
題目：給定一個未排序的整數數組 nums，找出數字連續的最長序列（不要求序列元素在原數組中連續）的長度。
要求：時間復雜度為 O(n)。
示例：
輸入：nums = [100, 4, 200, 1, 3, 2]
輸出：4
解釋：最長連續序列是 [1, 2, 3, 4]，長度為 4。
二、解法分析：從暴力到最優
方法一：暴力法（直觀但超時）
思路
對每個數 x，檢查 x+1, x+2, ... 是否存在于數組中，記錄最長連續序列的長度。
代碼
public int longestConsecutive(int[] nums) {int longestStreak = 0;for (int num : nums) {int currentNum = num;int currentStreak = 1;while (arrayContains(nums, currentNum + 1)) {currentNum += 1;currentStreak += 1;}longestStreak = Math.max(longestStreak, currentStreak);}return longestStreak;
}private boolean arrayContains(int[] arr, int num) {for (int i = 0; i < arr.length; i++) {if (arr[i] == num) {return true;}}return false;
}
復雜度
- 時間復雜度：O(n3)
- 遍歷數組 O(n)
- 對每個數檢查后續 O(n)
- 每次檢查是否存在 O(n)
- 空間復雜度：O(1)
方法二：排序法（O(n log n)，不符合要求但易理解）
思路
先排序數組，再遍歷統計連續序列長度。
代碼
public int longestConsecutive(int[] nums) {if (nums.length == 0) return 0;Arrays.sort(nums);int longestStreak = 1;int currentStreak = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] != nums[i-1]) {if (nums[i] == nums[i-1] + 1) {currentStreak++;} else {longestStreak = Math.max(longestStreak, currentStreak);currentStreak = 1;}}}return Math.max(longestStreak, currentStreak);
}
復雜度
- 時間復雜度：O(n log n)（排序主導）
- 空間復雜度：O(1)（忽略排序的棧空間）
方法三：哈希表優化（O(n)，最優解）
思路
- 用哈希表存儲所有數：快速判斷某個數是否存在（O(1)）。
- 僅從序列起點開始計數：若
x-1不存在，則x是序列起點，開始向后計數。
代碼
public int longestConsecutive(int[] nums) {// 用 HashSet 存儲所有數，支持 O(1) 查詢Set<Integer> numSet = new HashSet<>();for (int num : nums) {numSet.add(num);}int longestStreak = 0;// 遍歷每個數，若它是序列起點，則向后計數for (int num : numSet) {// 若 num-1 不存在，則 num 是序列起點if (!numSet.contains(num - 1)) {int currentNum = num;int currentStreak = 1;// 持續檢查 currentNum+1 是否存在while (numSet.contains(currentNum + 1)) {currentNum += 1;currentStreak += 1;}longestStreak = Math.max(longestStreak, currentStreak);}}return longestStreak;
}
復雜度
- 時間復雜度：O(n)
- 每個數最多被訪問兩次（一次插入哈希表，一次計數）
- 空間復雜度：O(n)（哈希表存儲所有數）
三、最優解法的核心邏輯
1. 為什么用哈希表？
哈希表（HashSet）提供 O(1) 的查找效率，能快速判斷某個數是否存在，避免了暴力法中的嵌套循環。
2. 如何避免重復計數？
關鍵在于只從序列的起點開始計數。例如，對于序列 [1, 2, 3, 4]，我們只在遇到 1 時才開始向后計數，遇到 2, 3, 4 時直接跳過。
判斷條件：若 num-1 不存在于哈希表中，則 num 是序列起點。
四、記憶技巧：把代碼變成“尋寶游戲”
用場景化記憶法理解最優解法的核心邏輯：
1. 角色賦值
- 哈希表（numSet）：扮演“地圖”，標記所有寶藏位置（數字存在）。
- 遍歷過程：扮演“探險家”，在地圖上尋找寶藏。
- 序列起點：扮演“特殊寶藏”，只有找到它才能開啟連續挖掘。
2. 游戲規則
① 探險家拿到地圖（哈希表），標記所有寶藏位置。
② 探險家隨機站在一個數字位置上，檢查：
- 如果左邊一格（
num-1）沒有寶藏，則當前位置是“特殊寶藏”，可開啟連續挖掘； - 如果左邊有寶藏，則跳過當前位置（留給左邊的寶藏來挖掘）。
③ 挖到一個寶藏后，持續向右挖掘（檢查num+1），記錄最長連續挖掘長度。
3. 關鍵記憶點
- 只從序列起點開始挖掘 → 避免重復計數。
- 哈希表快速定位寶藏 → O(1) 查詢效率。
五、實戰拓展：變種題鞏固思路
- 允許重復元素：原題已自動處理（哈希表去重）。
- 返回具體序列：在計數時記錄起點和終點，最后構造序列。
- 雙向擴展：同時向前（
num-1, num-2, ...）和向后擴展，適用于“允許不連續但可排序”的場景。
通過“尋寶游戲”的場景記憶，最優解法的邏輯會變得非常直觀。記住：算法的本質是“用合適的數據結構優化操作”，本題中哈希表的作用不僅是存儲數據，更是為了快速判斷“起點”，從而避免重復計算。多思考這種“篩選起點”的思想，能幫助你解決更多類似問題。
)
