Question

剑指 Offer II 119. 最长连续序列

题目描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

 

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

 

提示：

• 0 <= nums.length <= 104
• -109 <= nums[i] <= 109

 

进阶：可以设计并实现时间复杂度为 O(n)_ _的解决方案吗？

 

注意：本题与主站 128 题相同： https://leetcode.cn/problems/longest-consecutive-sequence/

解法

方法一：排序

我们先将数组排序，然后用一个变量 $t$ 记录当前连续序列的长度，用一个变量 $ans$ 记录最长连续序列的长度。

接下来，我们从下标 $i=1$ 开始遍历数组，对于当前遍历到的元素 $nums[i]$：

• 如果 $nums[i]=nums[i-1]$，则说明当前元素重复，无需考虑；
• 如果 $nums[i]=nums[i-1]+1$，则说明当前元素可以接在上一个连续序列后面以形成更长的连续序列，我们更新 $t = t + 1$，然后更新答案 $ans = \max(ans, t)$；
• 否则，说明当前元素无法接在上一个连续序列后面，我们将 $t$ 重新置为 $1$。

最终，我们返回答案 $ans$ 即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组的长度。

class Solution:
  def longestConsecutive(self, nums: List[int]) -> int:
    n = len(nums)
    if n < 2:
      return n
    nums.sort()
    ans = t = 1
    for a, b in pairwise(nums):
      if a == b:
        continue
      if a + 1 == b:
        t += 1
        ans = max(ans, t)
      else:
        t = 1
    return ans

class Solution {
  public int longestConsecutive(int[] nums) {
    int n = nums.length;
    if (n < 2) {
      return n;
    }
    Arrays.sort(nums);
    int ans = 1, t = 1;
    for (int i = 1; i < n; ++i) {
      if (nums[i] == nums[i - 1]) {
        continue;
      }
      if (nums[i] == nums[i - 1] + 1) {
        ans = Math.max(ans, ++t);
      } else {
        t = 1;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int longestConsecutive(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) {
      return n;
    }
    sort(nums.begin(), nums.end());
    int ans = 1, t = 1;
    for (int i = 1; i < n; ++i) {
      if (nums[i] == nums[i - 1]) {
        continue;
      }
      if (nums[i] == nums[i - 1] + 1) {
        ans = max(ans, ++t);
      } else {
        t = 1;
      }
    }
    return ans;
  }
};

func longestConsecutive(nums []int) int {
  n := len(nums)
  if n < 2 {
    return n
  }
  sort.Ints(nums)
  ans, t := 1, 1
  for i, x := range nums[1:] {
    if x == nums[i] {
      continue
    }
    if x == nums[i]+1 {
      t++
      ans = max(ans, t)
    } else {
      t = 1
    }
  }
  return ans
}

function longestConsecutive(nums: number[]): number {
  const n = nums.length;
  if (n < 2) {
    return n;
  }
  let ans = 1;
  let t = 1;
  nums.sort((a, b) => a - b);
  for (let i = 1; i < n; ++i) {
    if (nums[i] === nums[i - 1]) {
      continue;
    }
    if (nums[i] === nums[i - 1] + 1) {
      ans = Math.max(ans, ++t);
    } else {
      t = 1;
    }
  }
  return ans;
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  const n = nums.length;
  if (n < 2) {
    return n;
  }
  nums.sort((a, b) => a - b);
  let ans = 1;
  let t = 1;
  for (let i = 1; i < n; ++i) {
    if (nums[i] === nums[i - 1]) {
      continue;
    }
    if (nums[i] === nums[i - 1] + 1) {
      ans = Math.max(ans, ++t);
    } else {
      t = 1;
    }
  }
  return ans;
};

方法二：哈希表

我们用哈希表存储数组中的所有元素，然后遍历数组中的每个元素 $x$，如果当前元素的前驱 $x-1$ 不在哈希表中，那么我们以当前元素为起点，不断尝试匹配 $x+1, x+2, x+3, \dots$，直到匹配不到为止，此时的匹配长度即为以 $x$ 为起点的最长连续序列长度，我们更新答案即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。

class Solution:
  def longestConsecutive(self, nums: List[int]) -> int:
    s = set(nums)
    ans = 0
    for x in nums:
      if x - 1 not in s:
        y = x + 1
        while y in s:
          y += 1
        ans = max(ans, y - x)
    return ans

class Solution {
  public int longestConsecutive(int[] nums) {
    Set<Integer> s = new HashSet<>();
    for (int x : nums) {
      s.add(x);
    }
    int ans = 0;
    for (int x : nums) {
      if (!s.contains(x - 1)) {
        int y = x + 1;
        while (s.contains(y)) {
          ++y;
        }
        ans = Math.max(ans, y - x);
      }
    }
    return ans;
  }
}

class Solution {
public:
  int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int ans = 0;
    for (int x : nums) {
      if (!s.count(x - 1)) {
        int y = x + 1;
        while (s.count(y)) {
          y++;
        }
        ans = max(ans, y - x);
      }
    }
    return ans;
  }
};

func longestConsecutive(nums []int) (ans int) {
  s := map[int]bool{}
  for _, x := range nums {
    s[x] = true
  }
  for _, x := range nums {
    if !s[x-1] {
      y := x + 1
      for s[y] {
        y++
      }
      ans = max(ans, y-x)
    }
  }
  return
}

function longestConsecutive(nums: number[]): number {
  const s: Set<number> = new Set(nums);
  let ans = 0;
  for (const x of s) {
    if (!s.has(x - 1)) {
      let y = x + 1;
      while (s.has(y)) {
        y++;
      }
      ans = Math.max(ans, y - x);
    }
  }
  return ans;
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  const s = new Set(nums);
  let ans = 0;
  for (const x of nums) {
    if (!s.has(x - 1)) {
      let y = x + 1;
      while (s.has(y)) {
        y++;
      }
      ans = Math.max(ans, y - x);
    }
  }
  return ans;
};