# **Leetcode筆記(Longest Consecutive Sequence)**

:::info
:information_source: 題目 : Longest Consecutive Sequence, 類型 : array , 等級 : medium
日期 : 2023/04/16，2023/06/27，2023/12/07，2024/04/07
:::

### 嘗試

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        record = set()
        for i in range(len(nums)):
            record.add(nums[i])
        
        longest = 0
        for num in nums:
            if (num - 1) not in record:
                length = 1 # 開始計算長度
                # 在集合中查找(num + length)，直到(num + length)不在集合中為止
                # 時間複雜度取決於最長序列的長度k，因此操作次數為O(k)
                while (num + length) in record:
                    length += 1
                longest = max(length, longest)
            continue
        
        return longest

2023/05/07

# 忘記解法 直接看
# 簡單來說就是把某個數字後檢查一下
# 看有多後面的數存在於list中

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        
        record = set(nums)
        max_length = 0

        for n in nums:
            if (n - 1) not in record:
                length = 1
                n_add = 1
                while (n + n_add) in record:
                    length += 1
                    n_add += 1

                max_length = max(max_length, length)
        
        return max_length

2023/06/27

(n - 1) not in record的時間複雜度是O(1)。因為在Python的集合中，通過哈希表實現了高效的查找操作
總時間複雜度為O(n)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        record = set(nums) # 把list轉成set執行比較快
        maxLen = 0
        for n in record:
            if (n - 1) not in record: # 這句的時間複雜度為O(1)
                length = 1
                add = 1
                while (n + add) in record:
                    length += 1
                    add += 1
                maxLen = max(maxLen, length)

        return maxLen

2023/12/07

"""
nums = [100,4,200,1,3,2]
add n into set

for 
while 
    1
    l += 1
"""

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        record = set()
        for n in nums:
            record.add(n)
        
        maxLength = 0
        for n in nums:
            # n - 1 的話 就代表後續會有人去處理現在這個n
            if n - 1 in record:
              continue
            length = 1
            while (n + 1) in record:
                n += 1
                length += 1
            maxLength = max(maxLength, length)
        
        return maxLength

2024/04/07
記得res要重新計算，需要有一個全域變數，因為可能有多種答案

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        record = set(nums)
        maxRes = 0
        for n in nums:
            if n + 1 in record:
                continue
            res = 1
            while n - 1 in record:
                res += 1
                n -= 1
            maxRes = max(maxRes, res)
        
        return maxRes    

---
### **優化**

第二個for循環對於每個元素進行以下操作：

* 檢查(num - 1)是否在集合中，時間複雜度為O(1)。
* 如果(num - 1)不在集合中，開始計算最長序列的長度。在集合中查找(num + length)，直到(num + length)不在集合中為止。時間複雜度取決於最長序列的長度k，因此操作次數為O(k)。
* 更新最長序列的長度，時間複雜度為O(1)。

因此，第二個for循環的總操作次數為O(nk)。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        record = set(nums)
        
        longest = 0
        for num in nums:
            if (num - 1) not in record:
                length = 1 # 開始計算長度
                # 在集合中查找(num + length)，直到(num + length)不在集合中為止
                # 時間複雜度取決於最長序列的長度k，因此操作次數為O(k)
                while (num + length) in record:
                    length += 1
                longest = max(length, longest)
            continue
        
        return longest

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success
把nums放進set中，可以簡化成record = set(nums)
:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=P6RZZMu_maU&ab_channel=NeetCode
Provided by. NeetCode

###### tags: `arrays` `medium` `leetcode`