LeetCode-128. 最长连续序列
题目来源
128. 最长连续序列
题目详情
给定一个未排序的整数数组 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
题解分析
解法一：哈希表
- 考虑到本题是求解最长连续序列，这与以前的子序列问题有点不同，这里的连续指的是数字本身大小的连续，所以可能使用动态规划有一定困难。
- 这题可以从另一个角度思考问题，因为总共输入的序列是定长的，只有这么多的元素在数组中，所以，我们可以先把这些元素存入HashMap中，表示元素是否存在。对于连续元素，则可以依次递增当前元素num，并判断递增后的元素是否也出现在HashMap中，如果出现则以当前元素开始的序列长度增一。
- 此外，本题需要满足时间复杂度为\(O(n)\)，所以使用枚举的方法可能会不满足条件，而且里面有很多情况是重复考虑的了。比如说，之前已经判断了num, num+1,num+2,...,num+n，那么下一次从num+1开始到num+n的元素就不需要再判断了，因为这些元素已经存在HashMap中了。
- 最后，本题需要注意的一个地方是，需要使用HashSet来去重，这里的连续元素指的是严格连续，不包括重复元素。
class Solution {
public int longestConsecutive(int[] nums) {
// 这里使用HashSet，而不是HashMap，因为Set可以用来去重
Set set = new HashSet<>();
for(int num : nums){
set.add(num);
}
int maxlength = 0;
for(int num : nums){
if(!set.contains(num - 1)){
int curn = num;
int length = 1;
while(set.contains(curn + 1)){
curn++;
length++;
}
maxlength = Math.max(maxlength, length);
}
}
return maxlength;
}
}
解法二：哈希表+动态规划
- 前面也提到了，本题与以前的子序列问题有点不同，使用动态规划可能比较困难，也很难想到状态转移方程。但是，这并不意味着不能使用动态规划。
- 这是一种非常巧妙的做法，与思路2相同的一点是也利用了Map减小遍历次数。但很重要的一点不同是其value表示的是num所在的连续区间长度。举个例子，当Map的key为5，value为3时，这就表明当前有一个包含5且长度为3的连续区间，当然有多种可能，可以是[3,5],[4,6],[5,7]。
- 具体做法是：
3.1 遍历nums数组中的所有数字num
3.2 当num是第一次出现时：- 分别获取到左相邻数字num-1的连续区间长度left和右相邻数字num+1的连续区间长度right；
- 计算得到当前的区间长度为curLen=left+right+1；
- 更新最长区间长度ans以及左右边界的区间长度。
class Solution {
public int longestConsecutive(int[] nums) {
HashMap map = new HashMap<>();
int maxlength = 0;
for(int num : nums){
if(!map.containsKey(num)){
// 取出该元素左区间的长度（当前元素作为右端点）
int left = map.getOrDefault(num-1, 0);
// 取出该元素右区间的长度（当前元素作为左端点）
int right = map.getOrDefault(num+1, 0);
int length = left + right + 1;
map.put(num, length);
// 更新原有左区间的左端点
map.put(num - left, length);
// 更新原来右区间的右端点
map.put(num + right, length);
maxlength = Math.max(maxlength, length);
}
}
return maxlength;
}
}