## Leetcod: longest continuous sequence (Python)

A good function 2020-11-13 02:57:14
leetcod longest continuous sequence python

## 1. Title Description

Given an array of unsorted integers , Find out the length of the longest continuous sequence .
The time complexity of the algorithm is required to be O(n).

Example :

Input : [100, 4, 200, 1, 3, 2]
Output : 4
explain : The longest continuous sequence is [1, 2, 3, 4]. Its length is 4.

## 2. Ideas

### Reference resources

https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/zui-chang-lian-xu-xu-lie-by-leetcode/

### 2.1 brutal force

Traverse nums Every number in the array , And take that number as the first number in a continuous sequence , Enumerate the following numbers , Until a number didn't appear in the original array . When enumerating to a number that is not in the array , The length of the record , And update the current optimal solution .

#### Will timeout

``````class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
res = 0
for i in nums:
count = 0
j = i
while j in nums:
count += 1
j += 1
res = max(res,count)
return res
``````

### 2.2 Prioritize , Look again

##### The time complexity is o（nlogn）
``````class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if nums == []:
return 0
nums.sort()
maxlen = 1
curlen = 1
for i in range(1,len(nums)):
if nums[i] != nums[i-1]: # If there are duplicate numbers , Length calculation 1
if nums[i] == nums[i-1]+1:
curlen += 1
maxlen = max(maxlen,curlen)
else:
maxlen = max(maxlen,curlen)
curlen = 1
return maxlen
``````

### 2.3 utilize set

Space for time , With the aid of a set aggregate , Optimize the method of violence .

``````class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
numset = set(nums)
maxlen = 0
for num in numset:
curlen = 1
if num - 1 not in numset:
# Only when num Is the endpoint of a sequence , It's going through a loop , The complexity is o（n+n）= o（n）
while num + 1 in numset:
curlen += 1
num += 1
maxlen = max(maxlen,curlen)
return maxlen
``````