一、题目
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
二、示例
2.1> 示例 1：
【输入】nums = [100,4,200,1,3,2]
【输出】4
【解释】最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
2.2> 示例 2：
【输入】nums = [0,3,7,2,5,8,4,6,0,1]
【输出】9
提示：
-
0<= nums.length <=10^5 -
-10^9<= nums[i] <=10^9
三、解题思路
根据本题的描述，一般来说，最容易想到的就是先将nums进行排序，然后再从排序后的数组头部开始遍历，如果存在nums[i]+1，则进行加1计数。只要不存在nums[i]+1，则从0开始重新执行计数操作。那么，每当发生了“断点”，则通过result = Math.max(result, count)来更新result值（result表示最长数字连续序列个数）。
但是由于本题目要求实现时间复杂度为 O(n) 的算法解决此问题，那么排序的做法我们就无法实现了。那么，我们还有什么别的方法来解决这道题吗？我们可以创建一个Set数据结构的变量set，然后过滤掉nums数组中的重复元素。然后我们通过遍历数组nums，执行如下逻辑：
【case1】如果
nums[i]+1在set中存在，则表示nums[i]不是连续序列的最大值，那么我们继续向下遍历，不用做任何操作；
【case2】如果nums[i]+1在set中不存在，则表示nums[i]是连续序列的最大值，那么我们执行倒序查找set中的元素，即：依次寻找nums[i]--的元素，并进行计数操作。
通过以上的操作，我们本质上就是去寻找连续序列的最大值，然后倒序寻找连续元素。对于非最大值，我们也不用处理，这样就可以加快查找速度了。当然，每次寻找完连续序列之后，再通过result = Math.max(result, count)来更新result值，那么最终结果就是本题要求的——最长数字连续序列长度了。
以上就是本题的解题思路了，还是按照惯例，我们以nums = [100,4,200,1,3,2]为例，看一下具体的处理流程。请见下图所示：
四、代码实现
class Solution {
public int longestConsecutive(int[] nums) {
int result = 0;
Set<Integer> set = new HashSet();
for (int num : nums) set.add(num);
for (int num : nums) {
if (!set.contains(num + 1)) {
int max = 0;
while(set.contains(num--)) max++;
result = Math.max(result, max);
}
}
return result;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论