最长连续序列

题目要求

设计一个算法，找出给定未排序整数数组 nums 中数字连续的最长序列的长度。这里的连续序列指的是，序列中的所有数字都可以按升序排列，且每个数字之间的差值为 1。注意，序列中的元素在原数组中不需要是连续的。算法的时间复杂度应为 O(n)。

解题思路

要在 O(n) 的时间复杂度内解决这个问题，我们可以使用哈希表（Hash Table）来存储数组中每个元素是否已经被访问过，以及它们是否可以作为连续序列的一部分。解题步骤如下：

初始化哈希表：遍历数组 nums，将每个元素作为键存入哈希表，值初始化为 false，表示该元素尚未被访问。
遍历数组：再次遍历数组 nums，对于每个元素，执行以下步骤：
- 如果当前元素已经被访问过（即哈希表中对应值为 true），则跳过，因为它已经被包含在了某个序列中。
- 如果当前元素未被访问过，将其作为可能的序列起点，向两边扩展：
  - 向左扩展：检查 num-1 是否存在于哈希表中，如果存在且未被访问过，继续向左扩展，直到找不到连续的数字为止。
  - 向右扩展：检查 num+1 是否存在于哈希表中，如果存在且未被访问过，继续向右扩展，直到找不到连续的数字为止。
- 在扩展过程中，更新哈希表中对应元素的值为 true，表示这些元素已经被访问过，且已经被包含在了当前考虑的序列中。
- 记录并更新最长序列的长度。
返回结果：遍历完成后，返回记录的最长序列的长度。

这个算法之所以能保证 O(n) 的时间复杂度，是因为每个元素最多被访问两次：一次是在初始化哈希表时，另一次是在可能的序列扩展时。由于序列扩展是从未访问过的元素开始的，因此不会有重复的工作。

Golang 版本

package main

import "fmt"

func longestConsecutive(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    numSet := make(map[int]bool)
    for _, num := range nums {
        numSet[num] = false
    }

    longestStreak := 0

    for num := range numSet {
        // 如果num-1存在，说明num不是序列的起点
        if _, ok := numSet[num-1]; !ok {
            currentNum := num
            currentStreak := 1

            // 向右扩展序列
            for {
                if _, ok := numSet[currentNum+1]; ok {
                    currentNum++
                    currentStreak++
                } else {
                    break
                }
            }

            // 更新最长序列长度
            if currentStreak > longestStreak {
                longestStreak = currentStreak
            }
        }
    }

    return longestStreak
}

func main() {
    nums := []int{100, 4, 200, 1, 3, 2}
    fmt.Println(longestConsecutive(nums)) // 输出最长连续序列的长度
}

这段代码实现了题目要求的功能，首先创建一个哈希表来记录所有数字是否被访问过，然后遍历数组，对于每个作为新序列起点的数字（即前一个数字不存在的数字），向右扩展序列，最后返回找到的最长序列的长度。

C++版本

#include <iostream>
#include <vector>
#include <unordered_set>

int longestConsecutive(const std::vector<int>& nums) {
    std::unordered_set<int> num_set(nums.begin(), nums.end());
    int longestStreak = 0;

    for (int num : num_set) {
        // 如果num-1不存在，num可能是新序列的起点
        if (num_set.find(num - 1) == num_set.end()) {
            int currentNum = num;
            int currentStreak = 1;

            // 向右扩展序列
            while (num_set.find(currentNum + 1) != num_set.end()) {
                currentNum += 1;
                currentStreak += 1;
            }

            // 更新最长序列长度
            longestStreak = std::max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
}

int main() {
    std::vector<int> nums = {100, 4, 200, 1, 3, 2};
    std::cout << longestConsecutive(nums) << std::endl; // 输出最长连续序列的长度
    return 0;
}

这段 C++代码实现了相同的逻辑：使用一个无序集合（std::unordered_set）来存储所有的数字，并且迭代集合中的每个数字，如果当前数字的前一个数字不存在，则认为它可能是连续序列的起点，然后向右扩展序列，最后返回最长的序列长度。

Python 版本

def longest_consecutive(nums):
    num_set = set(nums)
    longest_streak = 0

    for num in num_set:
        # 如果num-1不存在，num可能是新序列的起点
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1

            # 向右扩展序列
            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1

            # 更新最长序列长度
            longest_streak = max(longest_streak, current_streak)

    return longest_streak

# 示例
nums = [100, 4, 200, 1, 3, 2]
print(longest_consecutive(nums))  # 输出最长连续序列的长度

这段 Python 代码遵循了之前描述的算法逻辑：首先将所有数字存入一个集合中，然后遍历集合，对于每个可能成为序列起点的数字（即前一个数字不存在的数字），向右扩展序列，最后返回最长序列的长度。

Java 版本

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int longestStreak = 0;

        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(solution.longestConsecutive(nums)); // 输出最长连续序列的长度
    }
}

这段 Java 代码实现了相同的算法逻辑：首先将所有数字添加到一个 HashSet 中，然后遍历这个集合，对于每个可能成为序列起点的数字（即前一个数字不存在的数字），向右扩展序列，最后返回最长序列的长度。

Rust 版本

use std::collections::HashSet;

fn longest_consecutive(nums: Vec<i32>) -> i32 {
    let num_set: HashSet<i32> = nums.into_iter().collect();
    let mut longest_streak = 0;

    for &num in num_set.iter() {
        if !num_set.contains(&(num - 1)) {
            let mut current_num = num;
            let mut current_streak = 1;

            while num_set.contains(&(current_num + 1)) {
                current_num += 1;
                current_streak += 1;
            }

            longest_streak = longest_streak.max(current_streak);
        }
    }

    longest_streak
}

fn main() {
    let nums = vec![100, 4, 200, 1, 3, 2];
    println!("{}", longest_consecutive(nums)); // 输出最长连续序列的长度
}

这段 Rust 代码实现了之前描述的算法逻辑：首先将所有数字存入一个 HashSet 中，然后遍历这个集合，对于每个可能成为序列起点的数字（即前一个数字不存在的数字），向右扩展序列，最后返回最长序列的长度。

总结

上述问题的解法在不同编程语言中的实现核心思想是一致的，即通过使用哈希表（在不同语言中可能是 HashSet、HashMap、Dictionary 或其他数据结构）来达到 O(n)时间复杂度的要求。解法的步骤可以总结如下：

创建哈希表：首先将所有的整数存入哈希表中，这样可以在 O(1)的时间复杂度内查询任何一个数是否存在。
寻找序列起点：遍历哈希表中的每个数字，对于每个数字，检查其前一个数字（即当前数字减一）是否存在于哈希表中。如果不存在，说明当前数字可能是一个连续序列的起点。
向右扩展序列：从当前序列的起点开始，不断检查下一个连续的数字（即当前数字加一）是否存在于哈希表中，如果存在，则序列可以继续向右扩展。同时，更新当前序列的长度。
更新最长序列长度：每次序列扩展结束后，如果当前序列的长度超过了之前记录的最长序列长度，则进行更新。
返回结果：所有数字遍历完成后，返回记录的最长序列长度作为结果。

这种解法的优势在于不需要对数组进行排序，从而避免了 O(n log n)的排序时间复杂度，实现了对时间复杂度的优化。不同编程语言的实现差异主要在于语法和数据结构的使用上，但算法的本质是相同的。

hot-100