题目描述

image.png

解题思路

哈希表

注意：请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

所以排序不行，排序时间复杂度O(nlogn)。
官解：
image.png
本题的是要找出连续的子序列，所以我们可以把所有数字添加到hash表中，遍历数组nums[i]，如果hash表中没有nums[i] - 1，那么表示它前边不连续，所以我们可以使用这个数字再hash表中查找他的递增序列，nums[i] + 1，nums[i]+2…，直到找到hash表中没有为止，此时使用计数器记录子序列长度。

  1. // 哈希表
  2. public int longestConsecutive(int[] nums) {
  3.     Set<Integer> set = new HashSet<>();
  4.     for (int i = 0; i < nums.length; i++) {
  5.         set.add(nums[i]);
  6.     }
  8.     int longestStreak = 0;
  10.     for (int num : nums) {
  11.         // 当不存在num-1的数字，此时就可以递增寻找
  12.         if (!set.contains(num - 1)) {
  14.             int currentNum = num;
  15.             int currentStreak = 1;
  17.             // 一直循环递增，记录自增子序列的长度
  18.             while (set.contains(currentNum + 1)) {
  19.                 currentNum += 1;
  20.                 currentStreak += 1;
  21.             }
  23.             // 取最大的序列长度
  24.             longestStreak = Math.max(currentStreak, longestStreak);
  25.         }
  26.     }
  28.     return longestStreak;
  29. }

image.png
由于是找到了没有nums[i]-1，才进入内层循环。
例如：100，4，200，1，3，2
只有100，200，1才会进入内层继续查找递增序列。4，3，2都能找到比他小1的数，所以不查找，而是加入hash表。