128. Longest Consecutive Sequence - Medium

前往題目

想法

• 沒什麼頭緒，用tree好像也怪怪的，因為沒辦法馬上判斷是否連貫
• 題目看起來很簡單，所以應該有一個很好用的演算法

思路

這題的關鍵: 使用Set

1. 把array轉換成set
2. 尋找sequence的開頭(也就是左邊沒有相鄰的數字，例如2如果是開頭，那set中絕對不會有1)
3. 找到開頭後，+1+1的找該sequence有多長

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> numSet = new HashSet();
        // Add to the set
        for (int num : nums) {
            numSet.add(num);
        }

        int longest = 0;

        for (int num : nums) {

            int length = 0;
            // Found a head number
            if (!numSet.contains(num - 1)) {
                // Keep traversing to see the sequence length
                while (numSet.contains(num + length)) {
                    ++length;
                }
            }
            longest = Math.max(longest, length);
        }
        return longest;
    }
}

2024/04/27

• 有想到要用hashset，但沒意識到可以用來檢查是否為頭數字