題目 : 128. Longest Consecutive Sequence Medium
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
1.
numSet : 用set()函數將nums做成集合,去除重複的數字
longest : 紀錄目前最大長度
length : 記錄由num開始算連續數字的長度
line 8 : 先看num是不是連續整數中的最小數,如果是就開始往後找num+1、num+2....
直到找到連續整數的最大長度
line 12 : 跳出迴圈後查看紀錄的length和longest那個最大,用max()回傳最大長度
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
numSet = set(nums)
longest = 0
for num in nums :
if num-1 not in numSet:
length = 0
while (num+length) in numSet:
length += 1
longest = max(length,longest)
return longest