P95 最长连续整数序列的长度

描述#

这个题目说的是，给你一个无序的整数数组，你要找到数组中元素能够组成的最长连续整数序列，然后返回它的长度。

比如说，给你的数组是 8, 4, 2, 1, 2, 3, 6，这里面的数字能够组成的最长连续整数序列是 1, 2, 3, 4，因此你要返回它的长度 4。

代码#

public class AlgoCasts {

  // Time: O(n*log(n)), Space: O(1)
  public int lengthOfLongestConsecutiveSequenceSorting(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    Arrays.sort(nums);
    int max = 0, p = 0;

    while (p < nums.length) {
      int len = 1;
      while (p < nums.length-1) {
        if (nums[p+1] - nums[p] > 1) break;
        if (nums[p+1] - nums[p] == 1) ++len;
        ++p;
      }
      max = Math.max(max, len);
      ++p;
    }
    return max;
  }

  // Time: O(n), Space: O(n)
  public int lengthOfLongestConsecutiveSequenceSet(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    Set<Integer> set = new HashSet<>();
    int max = 0;
    for (int num: nums) set.add(num);

    for (int i = 0; i < nums.length && !set.isEmpty(); ++i) {
      set.remove(nums[i]);
      int low = nums[i], high = nums[i];
      while (set.contains(--low)) set.remove(low);
      while (set.contains(++high)) set.remove(high);
      max = Math.max(max, high - low - 1);
    }
    return max;
  }

}