LeetCode128.最长连续序列
此题为大厂面试高频手撕题，希望大家能重视这道题。
题目大意
给定一个未排序的整数数组nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
思路分析
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
一些不是O(n)的方法就不说了。
那么对于连续的数字来说，重复的元素不是我们关心的，第一步可以去重。
要寻找一条连续的序列，还是免不了遍历一遍数据，那怎么减少遍历的次数那？答案就是我们可以从连续序列的第一个值开始。然后接着求num+1, num+2, num+3…num+n，所求的最大的n就是我们相要的结果n+1。
代码示例
Java版本
class Solution {public int longestConsecutive(int[] nums) {if(nums.length == 0) return 0;Set<Integer> set = new HashSet<>();for(Integer i: nums){set.add(i);}int max = 0;for (int num : nums) {if (!set.contains(num-1)){int inum = num;int index = 1;while(set.contains(inum+1)){inum++;index++;set.remove(inum);}max = Math.max(max,index);}}return max;}
}
Python版本
class Solution:def longestConsecutive(self, nums: List[int]) -> int:nums_set = set(nums)max_len = 0for num in nums:if (num-1) not in nums_set:n = numindex = 1while (n+1) in nums_set:index += 1n += 1nums_set.remove(n)max_len = max(max_len, index)return max_len
上面虽然是有for和while但是因为有判断(num-1) not in nums_set，所以说for循环中只会寻找连续序列中的第一个值，while中寻找后面的连续序列，本质上时间复杂度还是O(n)。