题目

题目

思路

哈希表

我们考虑枚举数组中的每个数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;
  }
}