题目
题目
思路
哈希表
我们考虑枚举数组中的每个数x，考虑以其为起点，不断尝试匹配x + 1, x + 2, ...是否存在，假设最长匹配到了x + y，那么以x为起点的最长连续序列即为x, x + 1, x + 2, ... , x + y，其长度为y + 1，我们不断枚举并更新答案即可
对于匹配的过程，暴力的方法是O(n)遍历数组去看是否存在这个数。改进是用一个哈希表存储数组中的数，这样查看一个数是否存在即能优化至O(1)的时间复杂度
跳过不必要的情况：已知有一个x, x + 1, x + 2, ... , x + y的连续序列，则不用从x + 1, x + 2或x + y开始尝试匹配。即我们要枚举的数x一定是在数组中不存在前驱数x - 1的。
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<>();
for (int num : nums) {
num_set.add(num);
}
int res = 0;
for (int num : num_set) {
if (!num_set.contains(num - 1)) {
int curNum = num;
int curStreak = 1;
while (num_set.contains(curNum + curStreak)) {
curNum += 1;
curStreak += 1;
}
res = Math.max(res, curStreak);
}
}
return res;
}
}
