###### tags: `Leetcode` `medium` `hash` `python` `Top 100 Liked Questions`

# 128. Longest Consecutive Sequence

## [題目連結:] https://leetcode.com/problems/longest-consecutive-sequence/

## 題目:
Given an unsorted array of integers ```nums```, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in ```O(n)``` time.

**Example 1:**

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

**Example 2:**

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

## 解題想法:
* 求最長連續數字的長度
* 要求runtime: O(n)
* 使用set()來去除重複!
* find
* insert
* delete
* O(1) in set

* 做法:
* Linear遍歷數組
* 當遍歷到x，**查set中是否有前一數(x-1)**，**若沒有，則才要進行下列判斷**，否則若(x-1)存在於set，continue!!
* 若沒有表示當前x自己當起始頭
* 紀錄當前最長長度=1
* 進while判斷x+1是否在set中
* 長度+1
* x=x+1重複loop
* **雖然有迴圈，但是每個元素最多只會被訪問兩次!!**
* 一次是在查set中是否有前一數(x-1)時
* 一次是面對真正起始位置x，開始計算後續符合x+1時
* 更新res

* trace:

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

val = 100
看100-1=99
if 99 not in nums_set:
yes
    while 101? 不在:
    ->cur_long=1

val = 4
看4-1=3
if 3 not in nums_set?
no!! 3存在於nums中!! 所以跳過此回合，進行下個for val值

val=200
if 199 not in nums_set: 
yes
    while 201? 不在:
    ->cur_long=1

val =1
if 0 not in nums_set:
    while 2.3.4..
    ->cur_long=4

val =3
if 2 not in nums_set?
no!! 進行下個for

val=2
if 1 not in nums_set?
no 結束迴圈

final cur_long=4

## Python:

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #用set去除重複
        long_sum = 0
        nums_set = set(nums)
        #遍歷set中所有數
        for val in nums_set:
            #若前一數不在 表示自己可以當頭計算
            if val-1 not in nums_set:
                #記錄當前值與當前最長連續
                cur_val = val
                cur_long = 1
                #每個元素最多訪問2次
                while cur_val+1 in nums_set:
                    cur_val+=1
                    cur_long+=1
                long_sum = max(long_sum,cur_long)
        return long_sum

result = Solution()
nums = [100,4,200,1,3,2]
ans = result.longestConsecutive(nums)
print(ans)