题目描述
思路
将数组所有点映射到一个数轴上，可以发现问题变为求每段区间首元素到尾元素的长度的最大值。
区间的长度：区间尾元素值-区间首元素值 + 1
方法一：超出时间限制
这个方法是最初自己想到的，但是超时了，主要原因是程序会有冗余的遍历过程，增加了开销。
思路：(时间复杂度太高)
- 先把所有元素加入到哈希表中
- 遍历每一个元素n，看是否存在n+1，更新res
- 求最大res
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
// 定义一个哈希表
Set<Integer> set = new HashSet<>();
// ：将所有数添加到哈希表中
for (int i : nums) set.add(i);
int res = 0;
for (int i = 0; i < nums.length; i ++) {
int n = nums[i] + 1;
while (set.contains(n)) {
len = len + 1;
n = n + 1;
}
res = Math.max(res, len);
}
return res;
}
}
方法二：哈希表
求每段区间首元素到尾元素的长度的最大值
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
Set<Integer> set = new HashSet<>();
for (int i : nums) set.add(i);
int res = 0;
for (int num : nums) {
if(!set.contains(num - 1)) {
// 说明是区间的首元素
int x = num;
while(set.contains(x + 1)) {
x ++;
}
res = Math.max(res, x - num + 1);
}
}
return res;
}
}