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).
Input : [100, 4, 200, 1, 3, 2]
Output : 4
explain : The longest continuous sequence is [1, 2, 3, 4]. Its length is 4.
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 .
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
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
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