给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。思路1: 暴力 O(n^2)， 哈希查找
遍历nums中的每一个元素item，判断以它作为开始元素的最长递增序列 依次判断item + 1是否在nums数组中思路2: 优先队列 + 哈希表 O(nlogn)
遍历nums中的每一个元素item，将其加入到优先队列q中遍历nums中的每一个元素item，将其加入到字典d中遍历优先队列中的元素item, 依次更新以item作为结束的值: d2[item] = d2.get(item-1, 0) + 1具体查看以下代码:
from queue import PriorityQueue class Solution: def longestConsecutive(self, nums: List[int]) -> int: d = {} q = PriorityQueue() for num in nums: d[num] = 1 q.put(num) while q.qsize() > 0: val = q.get() d[val] = d.get(val-1, 0) + 1 res = 0 for key, val in d.items(): if val > res: res = val return res思路3: 排序, O(nlogn)
排序数组从index=1的位置依次遍历数组中元素item，并计算以item作为开始元素的最大连续序列 如果 nums[index] == nums[index-1], index += 1如果 nums[index] == nums[index-1] + 1, index += 1, count += 1如果 nums[index] != nums[index-1] + 1, 更新最大值，并重置 count = 1, index += 1 更新最大值(这里是因为如果nums本身是连续的，那么在遍历的时候就一直不会被更新)代码如下:
class Solution: def longestConsecutive(self, nums: List[int]) -> int: if not nums: return 0 nums.sort() res, count = 1, 1 i = 1 while i < len(nums): if nums[i] == nums[i-1]: i += 1 continue if nums[i] == nums[i-1] + 1: count += 1 else: res = max(count, res) count = 1 i += 1 res = max(count, res) return res思路4: 哈希 + 优化遍历策略, O(nlogn)
将nums加入到哈希表，可以使用python里的set实现依次遍历set中的元素item, 如果 item - 1 在set中，直接跳过，因为以item开始的连续序列一定不是最大的从item开始搜索，如果item + 1在set中，count += 1, 否则更新最大更新序代码如下:
class Solution: def longestConsecutive(self, nums: List[int]) -> int: if not nums: return 0 nums_set = set(nums) res = 1 for num in nums_set: if num - 1 not in nums_set: count = 1 while num + 1 in nums_set: num += 1 count += 1 res = max(count, res) return res