最长连续序列

在本教程中，我们将编写 Python 程序来查找最长连续序列。这是技术面试中经常问到的一个编程问题。

最长连续序列问题通常涉及在一个整数数组或列表中查找最长的连续数字序列。其思想是确定没有间隙的最长连续数字序列的长度。

示例 1

解决方案

我们将使用各种方法来解决这个问题 -

朴素方法

该方法包括对数组进行排序，删除重复项，然后进行迭代。在迭代过程中，我们维护两个计数器：`count` 和 `max`，都初始化为零。在循环中，如果当前元素不比前一个元素大一，我们将 `count` 重置为一；否则，我们将其递增。每一步，我们都用 `count` 和当前 `max` 之间的最大值更新 `max`。

让我们理解以下示例 -

示例 -

输出

The length of the longest consecutive subsequence in input_arr1 is: 4
The length of the longest consecutive subsequence in input_arr2 is: 5

解释 -

我们对数字列表进行排序，以便更容易识别连续元素。

我们将 `count` 初始化为 1，以跟踪当前连续序列的长度，并将 `max_count` 初始化为 1，以存储最长的连续序列的长度。

我们迭代排序后的数字列表，并检查当前元素是否不等于前一个元素加一。如果它们不连续，我们将 `count` 重置为 1。否则，我们递增 `count`。我们用 `max_count` 的当前值和 `count` 之间的最大值来更新 `max_count`。

最后，我们返回 `max_count`，它代表输入列表中最长连续子序列的长度。

时间复杂度 - O(n log n)，其中 n 是输入列表中的元素数量。

辅助空间： O(N)。存储不重复元素需要额外的空间。

使用排序查找最长连续子序列，不删除重复元素

该方法包括先对数组进行排序。随后，我们计算排序数组中连续元素的数量，不包括任何重复的元素。让我们通过以下示例来理解 -

示例 -

输出

The length of the longest consecutive subsequence in input_arr1 is: 4
The length of the longest consecutive subsequence in input_arr2 is: 5

解释 -

代码首先对输入的数字列表进行排序，以便更容易识别连续元素。初始化了两个变量 `longest_sequence` 和 `current_sequence`，它们都设置为 1。这些变量分别用于跟踪迄今为止找到的最长连续子序列的长度以及正在检查的当前连续子序列的长度。

然后迭代排序后的列表并检查连续元素。如果当前元素正好比前一个元素大一，则递增 `current_sequence`，因为它表示一个连续元素。如果当前元素与前一个元素不同，这意味着它不是重复项，则将 `current_sequence` 重置为 1，以开始计算新的潜在连续子序列。

在每次迭代之后，代码都会用其当前值和 `current_sequence` 之间的最大值来更新 `longest_sequence`。这确保了它跟踪迄今为止找到的最长连续子序列。

最后，该函数返回 `longest_sequence` 的值，该值表示输入列表中最长连续子序列的长度。

使用哈希查找最长连续子序列

要使用哈希查找最长连续子序列，您可以采用一种更有效的方法，该方法不涉及排序。以下是使用哈希实现此目的的 Python 程序。

示例 -

输出

The length of the longest consecutive subsequence in input_arr1 is: 4
The length of the longest consecutive subsequence in input_arr2 is: 5

解释 -

我们首先将输入列表 `nums` 转换为一个名为 `num_set` 的集合，以便进行更快的查找。

我们将 `longest_sequence` 初始化为 0，它将存储最长连续子序列的长度。

我们迭代 `num_set` 中的元素，并对于每个元素，我们检查 `num - 1` 是否不在 `num_set` 中。如果不存在，则表示 `num` 是一个潜在连续序列的开始。

在循环内部，我们将 `current_num` 初始化为当前元素 `num`，并将 `current_sequence` 初始化为 1。然后，我们使用 while 循环向前检查连续数字（即 `current_num + 1`）并相应地递增 `current_sequence`。

我们将 `longest_sequence` 更新为它当前值和 `current_sequence` 之间的最大值。这确保了我们跟踪迄今为止找到的最长连续子序列。

最后，我们返回 `longest_sequence` 的值，它代表输入列表 `nums` 中最长连续子序列的长度。