題目

他說他會給一個沒有排序過的整數陣列，然後們要回傳這個整數陣列可以湊成連續數列的長度。
然後他還規定我的時間複雜度一定要是O(n)。

Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
因為這個陣列裡可以排出[1,2,3,4]，長度是4個，所以回傳 4。

Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
那如果像example2這樣有從婦的數字出現的話也只要取一個就好，不可以[0,0,1,2,3,4,5,6,7,8]。

Hash Set

因為這題要去除重複的元素，還需要判斷某一個數字存不存在，所以呢我們來認識一下Hash
Set吧。
它可以應用的情況:
* 去掉重複的元素或單詞
* 快速搜尋和檢查
* 搜尋共有的元素或獨有的元素
它的特點:
* 唯一性
* 無序性
* 時間複雜度為O(1)

那這是gpt給我的簡單的看Hash Set的用法

import java.util.HashSet;
import java.util.Set;

public class Demo {
    public static void main(String[] args) {
        // 建立 HashSet
        Set<Integer> set = new HashSet<>();

        // 加入元素
        set.add(10);
        set.add(20);
        set.add(30);
        set.add(20); // 重複的會被忽略

        System.out.println(set); // [20, 10, 30] (順序不一定)

        // 判斷元素是否存在
        System.out.println(set.contains(20)); // true
        System.out.println(set.contains(40)); // false

        // 移除元素
        set.remove(10);
        System.out.println(set); // [20, 30]

        // 取得大小
        System.out.println(set.size()); // 2

        // 遍歷 HashSet
        for (int num : set) {
            System.out.println(num);
        }
    }
}

想法

那我們要找最長的連續序列，要檢查數字是否連續但又不能排序，因為題目要求複雜度要O(n)，還要有一個結構判斷某個數字是否存在。所以我選擇用Hash Set來解題，好處是找數字是否存在的複雜度是O(1)。然後把所有元素放進去之後就可以知道這個元素的後面+1、+2...是否存在。
所以我們先把所有數字先存在Hash Set來消掉重複的數字，然後如果數字-1不存在，就代表他是一個連續陣列的頭，然後再用while迴圈來不斷檢查現在的數字+1有沒有存在，最後算連續陣列的長度。

程式碼

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;

        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int longest = 0;
        for (int num : set) {
            // 判斷開頭
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int streak = 1;

                //一直檢查現在的數字+1有沒有存在
                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    streak++;
                }

                longest = Math.max(longest, streak);
            }
        }

        return longest;
    }
}

執行成功畫面

參考資料:
https://refblogs.com/article/503#google_vignette
https://ithelp.ithome.com.tw/articles/10246991
https://ithelp.ithome.com.tw/articles/10229527