vvrf / DSA.log

问题拆解

给一个未排序的整数数组，找出数字上连续（如 1, 2, 3, 4）的最长序列长度，元素在数组里的位置无关紧要，要求 O(n)。

最自然的做法是排序后扫一遍数相邻差 1 的段，但排序是 O(n log n)，题目明确不让过这条线。既然“连续”说的是数值相邻，判断 v + 1 存不存在就是一次哈希查询——把所有数丢进哈希集合，从任意数出发不断问“下一个在吗”，就能沿着序列往右数。

但只做到这一步还不够。如果对每个数都往右数一遍，[1, 2, 3, ..., n] 这样的数组会让 1 起跑数 n 步、2 起跑数 n-1 步……总量 O(n²)。问题出在同一段序列被它的每个成员重复数了。修正办法只有一行：起跑前先查 v - 1，它在集合里就说明 v 不是这段的起点，直接跳过，让真正的起点去数。

每段连续序列有且只有一个起点——那个左邻居不存在的数。只从起点起跑，每个元素一生只被“数”一次，总步数才守得住 O(n)。

哈希集合 + 只从起点起跑

先把数组去重进集合（重复值对“连续”没贡献），再遍历集合：跳过非起点，从起点沿 v + 1 一路数到断。注意外层遍历集合而不是原数组——原数组若有大量重复值，每个重复都会做一次“是不是起点”的查询，虽不影响渐进复杂度，但集合更干净。

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int v : nums) {
        set.add(v);
    }
    int best = 0;
    for (int v : set) {
        if (set.contains(v - 1)) {
            continue; // 不是起点，这段留给 v-1 那次去数
        }
        int cur = v;
        while (set.contains(cur + 1)) { // 沿序列向右数
            cur++;
        }
        best = Math.max(best, cur - v + 1);
    }
    return best;
}

def longestConsecutive(nums: List[int]) -> int:
    num_set = set(nums)
    best = 0
    for v in num_set:
        if v - 1 in num_set:
            continue  # 不是起点，这段留给 v-1 那次去数
        cur = v
        while cur + 1 in num_set:  # 沿序列向右数
            cur += 1
        best = max(best, cur - v + 1)
    return best

func longestConsecutive(nums []int) int {
    set := make(map[int]struct{}, len(nums))
    for _, v := range nums {
        set[v] = struct{}{}
    }
    best := 0
    for v := range set {
        if _, ok := set[v-1]; ok {
            continue // 不是起点，这段留给 v-1 那次去数
        }
        cur := v
        for {
            if _, ok := set[cur+1]; !ok {
                break
            }
            cur++ // 沿序列向右数
        }
        best = max(best, cur-v+1)
    }
    return best
}

use std::collections::HashSet;

pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
    let set: HashSet<i32> = nums.into_iter().collect();
    let mut best = 0;
    for &v in &set {
        if set.contains(&(v - 1)) {
            continue; // 不是起点，这段留给 v-1 那次去数
        }
        let mut cur = v;
        while set.contains(&(cur + 1)) { // 沿序列向右数
            cur += 1;
        }
        best = best.max(cur - v + 1);
    }
    best
}

为什么这段代码是 O(n) 而不是看上去的两层循环 O(n²)？用摊还的眼光看：内层 while 的每一步都把某个元素“数进”一段序列，而每个元素只属于一段序列、且这段只从唯一的起点被数一次，所以全部内层步数加起来不超过 n。没有起点检查时这个论证不成立，复杂度立刻塌回平方——这道题的全部分量就压在 contains(v - 1) 这一行上。

复杂度

指标	复杂度	原因
时间	`O(n)`	建集合 O(n)；每个元素至多被起点起跑数到一次（摊还）
空间	`O(n)`	哈希集合存所有不同的值

可以迁移的模式

“数值上的相邻关系”可以用哈希集合的 O(1) 查询代替排序来发现；
遍历中会重复处理同一组对象时，为每组指定唯一代表（这里是序列起点），只让代表干活；
两层循环不一定是 O(n²)：内层总步数能摊还到每个元素常数次，整体依然线性。

“找到组的天然代表、其余成员绕行”这个手法，在并查集和区间合并类问题里还会反复出现。