本文共 1061 字，大约阅读时间需要 3 分钟。

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？

示例 1：输入：nums = [100,4,200,1,3,2]

输出：4

解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]

输出：9

提示：

0 <= nums.length <= 104

-109 <= nums[i] <= 109

解题思路：用数据结构hashset来解决该问题，去重；然后为了进一步缩小计算量，如果该值存在前缀，无需计算，因为最长的值肯定在其前缀中存在。

package com.lcz.leetcode;// 最长连续序列import java.util.*;public class Leetcode128 {
   	class Solution {
   	    public int longestConsecutive(int[] nums) {
   	    	// 用hashset来去重	    	HashSet
   
     hashset = new HashSet<>();	    	for(int num:nums) {
   	    		hashset.add(num);	    	}	    	// 存储最终结果	    	int res = 0;	    	// 遍历hashset	    	for(int num:hashset) {
   	    		// 只判断其没有前缀的 如果其有前缀，那么最长值肯定在前缀	    		if(!hashset.contains(num-1)) {
   	    			// 遍历	    			int currentNum = num;	    			int currentLength = 1;	    			// 找其后续	    			while(hashset.contains(currentNum+1)) {
   	    				currentLength += 1;	    				currentNum += 1;	    			}	    			// 更新	    			res = Math.max(res,currentLength);	    		}	    	}	    	return res;	    }	}}
   

转载地址：https://codingchaozhang.blog.csdn.net/article/details/111852062 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！