LeetCode刷题笔记：字节跳动-数组和排序(6)-最长连续序列

6.最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例一：

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

本题找的是最长连续序列，因此直接对原数组进行遍历，保持一个值a记录当前若为连续序列的值，保持一个值tmp记录当前最长连续序列长度，保持一个值mx记录最长连续序列长度。遍历时对比当前值与下一个遍历值是否相等，如果相等跳出此次循环进行下一次循环，如果a等于当前遍历值，tmp++，然后mx等于tmp和mx的最大值；如果当前值与下一个遍历值不相等，则将tmp置1，然后a++，代码如下：

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums==[]:
            return 0
        nums.sort()
        mx = 1
        tmp = 1
        a = nums[0]+1
        for i in range(1,len(nums)):
            if nums[i]==nums[i-1]:
                continue
            if a==nums[i]:
                tmp+=1
                mx = max(mx,tmp)
                a+=1
            else:
                tmp=1
                a=nums[i]+1
        return mx