題目
#

leetcode 128 - Longest Consecutive Sequence (題目說明請點連結)

題目簡述
#

給一個未排序的整數陣列 nums，返回最長的連續元素序列的長度。
要求演算法必須在 O(n) 時間複雜度內執行。

範例
#

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: 最長的連續元素序列是 [1,2,3,4]。因此其長度為 4。

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Explanation: 最長的連續元素序列是 [0,1,2,3,4,5,6,7,8]。因此其長度為 9。

解題思路
#

這題要求我們找到陣列中最長的連續序列。我們可以使用HashSet來儲存所有數字，然後對於每個數字，檢查它是否是一個連續序列的起點（即沒有比它小 1 的數字），如果是，則從該數字開始計算連續序列的長度。

解法
#

將所有數字加入 HashSet 中，方便 O(1) 查找
遍歷 HashSet 中的每個數字
對於每個數字，檢查它是否是一個連續序列的起點
如果是起點，則從該數字開始計算連續序列的長度
更新最長連續序列的長度
返回最長連續序列的長度

步驟
#

初始化：
- 創建 HashSet 儲存所有數字
- 初始化最長連續序列長度 longest = 0
尋找連續序列：
- 遍歷 HashSet 中的每個數字
- 檢查數字 n 是否為連續序列的起點（!set.contains(n-1)）
- 如果是起點，從 n 開始計算連續序列長度
計算序列長度：
- 使用 while 迴圈檢查 n+length 是否在 HashSet 中
- 更新最長連續序列長度
返回結果：
- 返回最長連續序列的長度

例子說明
#

nums = [100,4,200,1,3,2]

步驟	當前數字	是否為起點	連續序列	序列長度	最長長度
初始化	-	-	-	-	0
第 1 步	100	是（99 不在 set 中）	[100]	1	1
第 2 步	4	是（3 不在 set 中）	[4,3,2,1]	4	4
第 3 步	200	是（199 不在 set 中）	[200]	1	4
第 4 步	1	否（0 不在 set 中，但 1 已經被計算過）	-	-	4
第 5 步	3	否（2 在 set 中）	-	-	4
第 6 步	2	否（1 在 set 中）	-	-	4

最終結果： 4

連續序列說明：

序列 [100]：長度為 1
序列 [1,2,3,4]：長度為 4（最長）
序列 [200]：長度為 1

完整程式碼
#

java

class Solution {
    public int longestConsecutive(int[] nums) {
        // 創建 HashSet 儲存所有數字，方便 O(1) 查找
        Set<Integer> set = new HashSet<>();
       
        // 將所有數字加入 HashSet
        for(int n:nums){
            set.add(n);
        }

        // 初始化最長連續序列長度
        int longest = 0;
        
        // 遍歷 HashSet 中的每個數字
        for(int n:set){
            // 檢查數字 n 是否為連續序列的起點
            // 如果 set 中沒有 n-1，則 n 是起點
            if(!set.contains(n-1)){
                int length = 1;

                // 從 n 開始計算連續序列的長度
                while(set.contains(n+length)){
                    length ++;
                }

                // 更新最長連續序列的長度
                longest= Math.max(longest, length);
            }
         
        }

        return longest;
    }
}