目录
一、题目描述
给定一个未排序的整数数组 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 <= 105
-109 <= nums[i] <= 109
二、思路讲解
很容易想到：排序后按顺序找等差数列的长度就行了。
需要注意的一点是，如果相邻位置数字相同，则跳过。
三、Java代码实现
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length<=1){
return nums.length;
}
int count = 1; //一个等差数列的长度
int big = 1; //所有等差数列的最大长度
Arrays.sort(nums);
for(int i=0; i<=nums.length-2; i++){
int temp = nums[i+1]-nums[i];
if(temp==1){
count++;
} else if(temp==0 && count!=1){ //相邻位置数字相同，则直接跳过
} else {
big = Math.max(count, big);
count = 1;
}
}
big = Math.max(count, big);
return big;
}
}时间复杂度： O(NlogN)
空间复杂度： O(1)
四、思路优化
题目要求算法时间复杂度为 O(n)，我们想到使用hash表。hash表查找的时间复杂度为O(1)
将数字全部存入HashSet中，然后依次以每个数为等差数列的末尾，去集合中寻找小1的数字。如果找到，则再-1；如果找不到，则找下一个数字。
但是这样的做法，最坏情况会达到O(N^2)。我们需要进行一些判断。可以注意到，比如我们找的数字是4，然后依次去找3、2、1……，而假如nums中，还有一个3，那么我们还要再去找2、1、0……，事实上，找3以前的数字的这个操作早在找4的时候就已经做过了，就可以直接跳过了。
经过这样的优化，数组中的每个数字其实只被访问过一次，时间复杂度为 O(n)。
五、优化代码
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num : nums){
set.add(num);
}
int count = 1; //本次等差数列的长度
int big = 0; //所有等差数列的最大长度
for(int num : nums){
//如果集合中存在num+1，就放到算num+1的时候去算，这里就不做重复计算了
if(!set.contains(num+1)){
int temp = num - 1;
//不断去找集合中小1的数字
while(set.contains(temp)){
count++;
temp--;
}
big = Math.max(big, count);
count = 1;
}
}
return big;
}
}时间复杂度： O(N)
空间复杂度： O(N)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/124998.html
