算法-最长连续序列

leetcode的题目链接

这道题的思路主要是要求在O（n)的时间复杂度下，所以你暴力解决肯定不行，暴力至少两层for循环，所以要在O（n)的时间复杂度下，你可以使用HashSet来存储数组，对于每个数字，我们判断它的前一个数字在不在集合里面，如果在就再向前判断，不在就以这个为标准，开始向后遍历，一直到后面不是+1，停止，返回最大长度。

下面是代码

import java.util.HashSet;
import java.util.Set;public class Solution {public int longestConsecutive(int[] nums) {//给定一个数组 找出里面数字连续的最长序列 不要求序列元素在原数组中连续 注意时间复杂度为O（n)if(nums.length == 0){return 0;}Set<Integer>numset=new HashSet<>();for(int num:nums){numset.add(num);}int longStack=0;for(int num:nums){if(!numset.contains(num-1)) {int currentNum = num;int currentStack = 1;while (numset.contains(currentNum + 1)) {currentNum+=1;currentStack++;}longStack=Math.max(longStack, currentStack);}}return longStack;}
}