## leetcod：最长连续序列（python）

Python 最长 序列 连续 leetcod

## 2. 思路

### 参考

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

### 2.1 暴力穷举

#### 会超时

``````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 先排序，再找

##### 时间复杂度为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]: # 如果有重复的数字，长度算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 利用set

``````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:
# 只有当num是一个序列的端点时，在进行循环，复杂度为o（n+n）= o（n）
while num + 1 in numset:
curlen += 1
num += 1
maxlen = max(maxlen,curlen)
return maxlen
``````

https://blog.csdn.net/ggdhs/article/details/91364477