周末也要来刷题 128 ～ 最长的连续 subsequence

基本信息

• 题号：128
• 题厂：谷歌
• 难度系数：中

已知一个数组，问数组里面连续整数有多少个？

例如：nums = [100,4,200,1,3,2]
返回 4, 
因为[1, 2, 3, 4] 为连续整数，长度为 4

解题思路

• 算连续整数有多少个，很容易想到先把数组排序，然后遍历一遍前后比较；
• 涉及排序，于是时间复杂度为 O（n logn）

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 当数组长度小于或等于 1 时，无需排序。数组多长就有多少连续元素……提前返回
        if len(nums) <= 1:
            return len(nums)
        
        nums.sort()
        
        curStreak = 1
        longest = 0
        
        # 遍历时，如果当前元素和前面的元素连续（相差 1），连续计数器加 1
        # 如果当前元素和前面元素不连续（相差 1 以上），说明连续中断。这时重设连续计数器为 1，同时检查要返回的 longest 需不需要更新最大值……
        # 如果前后元素相等，那啥也不做，因为还没有进入连续区间
        for i in range(1, len(nums)):
            if nums[i] != nums[i -1]:
                if nums[i] == nums[i - 1] + 1:
                    curStreak += 1
                else:
                    longest = max(longest, curStreak)
                    curStreak = 1
                    
        return max(longest, curStreak)

最优解？？！！

以上先排序再计算连续个数的方法，貌似效率挺高。然而这并不是本题最优解……

题目要求时间复杂度要控制在 O（n）以内，于是还得继续想办法😵……这时 set 这种保证元素不重复的数据结构登场了……

我们通过查看与当前元素连续的整数是否在 set 内，来检测有多少个连续整数……

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest = 0
        num_set = set(nums)
        # 把数组转化为 set 后，遍历数组时，先找到「开头」（前元素与当前元素不连续）
        # 然后开始计算后元素是否在 set 内，如果在计数器➕1；如果不在跳出循环，更新最长连续记录……
        for n in nums:
            if n - 1 not in num_set:
                cur_n = n
                cur_streak = 1
                
                while (cur_n + 1) in num_set:
                    cur_n += 1
                    cur_streak += 1
                    
                longest = max(cur_streak, longest)
                
        return longest

Constraints

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

Big O（最优解）

• Time：O（n）
• Space：O（n）—— set 空间

测试

• 数列为空时
• 数列为 1 时
• 数列元素有重复时
• ……

总结

• 也是中规中矩中档题啊😭