基本信息

  • 题号：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


采用 set 算法后，也解题成功了 🙈


Constraints

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


Big O（最优解）

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


测试

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


总结

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