128. 最长连续序列

题目描述

输入一个未排序的整数数组 nums。

从数组中挑出一组数，使它们排好序后是一串每次加 1 的连续整数，例如 3,4,5,6。这些数在原数组中的位置不必相邻，重复的值只算一次。

返回这样的连续整数串最长能有多长。数组为空时返回 0。算法的时间复杂度需为 O(n)。

示例 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 到 8 全部出现，长度 9。

示例 3

输入：nums = [1,0,1,2]
输出：3

解释：去重后有 0,1,2，长度 3。

数据范围

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

解题思路：哈希集合找起点

将所有数放入集合。只有当 x-1 不在集合时，x 才是序列起点，再向上计数；每个数最多参与一次连续扩展。

为什么正确

每次扩展只从真正起点开始，因此不会为同一序列重复扫描前缀。

复杂度分析

平均时间 O(n)，空间 O(n)。

易错点

对每个数字都向上扩展会退化为 O(n²)，必须先判断 x-1 不存在。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def longestConsecutive(self, nums):
        s = set(nums)
        best = 0
        for x in s:
            if x - 1 not in s:
                y = x
                while y in s:
                    y += 1
                best = max(best, y - x)
        return best

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

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

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

var longestConsecutive = function(nums) {
    const s = new Set(nums);
    let best = 0;
    for (const x of s) {
        if (!s.has(x - 1)) {
            let y = x;
            while (s.has(y))
                y++;
            best = Math.max(best, y - x);
        }
    }
    return best;
};

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

载入编辑器，自己跑一遍 →

其他解法

哈希找起点和并查集都接近 O(n)，前者更简洁；排序法为 O(n log n)，最好写但不满足题目要求。

解法 2：排序后线性扫描时间 O(n log n)，空间 O(n)

先对数组排序。从左到右扫描，遇到重复元素直接跳过。若当前数等于前一个数加 1，当前长度加 1；否则重置为 1。扫描中的最大长度就是答案。

思路最直观，但不满足题目 O(n) 的要求。实际运行中常数较小，往往不比哈希慢。

class Solution:
    def longestConsecutive(self, nums):
        if not nums:
            return 0
        nums = sorted(nums)
        best = cur = 1
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                continue
            if nums[i] == nums[i - 1] + 1:
                cur += 1
            else:
                cur = 1
            best = max(best, cur)
        return best

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        int[] a = nums.clone();
        Arrays.sort(a);
        int best = 1, cur = 1;
        for (int i = 1; i < a.length; i++) {
            if (a[i] == a[i - 1]) continue;
            if ((long) a[i] == (long) a[i - 1] + 1) cur++;
            else cur = 1;
            best = Math.max(best, cur);
        }
        return best;
    }
}

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> a(nums);
        sort(a.begin(), a.end());
        int best = 1, cur = 1;
        for (int i = 1; i < (int)a.size(); i++) {
            if (a[i] == a[i - 1]) continue;
            if ((long long)a[i] == (long long)a[i - 1] + 1) cur++;
            else cur = 1;
            best = max(best, cur);
        }
        return best;
    }
};

func longestConsecutive(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	a := append([]int{}, nums...)
	sort.Ints(a)
	best, cur := 1, 1
	for i := 1; i < len(a); i++ {
		if a[i] == a[i-1] {
			continue
		}
		if a[i] == a[i-1]+1 {
			cur++
		} else {
			cur = 1
		}
		best = max(best, cur)
	}
	return best
}

var longestConsecutive = function(nums) {
    if (nums.length === 0) return 0;
    const a = [...nums].sort((x, y) => x - y);
    let best = 1, cur = 1;
    for (let i = 1; i < a.length; i++) {
        if (a[i] === a[i - 1]) continue;
        if (a[i] === a[i - 1] + 1) cur++;
        else cur = 1;
        best = Math.max(best, cur);
    }
    return best;
};

function longestConsecutive(nums: number[]): number {
    if (nums.length === 0) return 0;
    const a = [...nums].sort((x, y) => x - y);
    let best = 1, cur = 1;
    for (let i = 1; i < a.length; i++) {
        if (a[i] === a[i - 1]) continue;
        if (a[i] === a[i - 1] + 1) cur++;
        else cur = 1;
        best = Math.max(best, cur);
    }
    return best;
}

解法 3：并查集时间 O(n·α(n))，空间 O(n)

每个不同的数先自成一个集合，大小为 1。对每个 x，如果 x+1 也存在，就合并两者所在的集合，并累加大小。最后最大的集合大小就是最长连续序列的长度。

近似线性，且适合元素动态加入、需要随时查询的场景。需要额外的父节点和大小表，代码明显更长。

class Solution:
    def longestConsecutive(self, nums):
        parent = {x: x for x in nums}
        size = {x: 1 for x in parent}

        def find(x):
            root = x
            while parent[root] != root:
                root = parent[root]
            while parent[x] != root:
                parent[x], x = root, parent[x]
            return root

        best = 0
        for x in parent:
            if x + 1 in parent:
                a, b = find(x), find(x + 1)
                if a != b:
                    if size[a] < size[b]:
                        a, b = b, a
                    parent[b] = a
                    size[a] += size[b]
        for x in parent:
            if parent[x] == x:
                best = max(best, size[x])
        return best

class Solution {
    private Map<Integer, Integer> parent = new HashMap<>();
    private Map<Integer, Integer> size = new HashMap<>();

    private int find(int x) {
        int root = x;
        while (parent.get(root) != root) root = parent.get(root);
        while (parent.get(x) != root) {
            int next = parent.get(x);
            parent.put(x, root);
            x = next;
        }
        return root;
    }

    public int longestConsecutive(int[] nums) {
        parent.clear();
        size.clear();
        for (int x : nums) {
            parent.put(x, x);
            size.put(x, 1);
        }
        for (int x : new ArrayList<>(parent.keySet())) {
            if (x == Integer.MAX_VALUE || !parent.containsKey(x + 1)) continue;
            int a = find(x), b = find(x + 1);
            if (a == b) continue;
            if (size.get(a) < size.get(b)) {
                int t = a;
                a = b;
                b = t;
            }
            parent.put(b, a);
            size.put(a, size.get(a) + size.get(b));
        }
        int best = 0;
        for (int x : parent.keySet()) {
            if (parent.get(x) == x) best = Math.max(best, size.get(x));
        }
        return best;
    }
}

class Solution {
    unordered_map<int, int> parent, sz;
    int find(int x) {
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }
public:
    int longestConsecutive(vector<int>& nums) {
        parent.clear();
        sz.clear();
        for (int x : nums) {
            parent[x] = x;
            sz[x] = 1;
        }
        for (auto& [x, _] : parent) {
            if (x == INT_MAX || !parent.count(x + 1)) continue;
            int a = find(x), b = find(x + 1);
            if (a == b) continue;
            if (sz[a] < sz[b]) swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
        int best = 0;
        for (auto& [x, p] : parent) {
            if (p == x) best = max(best, sz[x]);
        }
        return best;
    }
};

func longestConsecutive(nums []int) int {
	parent := map[int]int{}
	size := map[int]int{}
	for _, x := range nums {
		parent[x] = x
		size[x] = 1
	}
	find := func(x int) int {
		root := x
		for parent[root] != root {
			root = parent[root]
		}
		for parent[x] != root {
			next := parent[x]
			parent[x] = root
			x = next
		}
		return root
	}
	keys := make([]int, 0, len(parent))
	for x := range parent {
		keys = append(keys, x)
	}
	for _, x := range keys {
		if _, ok := parent[x+1]; !ok {
			continue
		}
		a, b := find(x), find(x+1)
		if a == b {
			continue
		}
		if size[a] < size[b] {
			a, b = b, a
		}
		parent[b] = a
		size[a] += size[b]
	}
	best := 0
	for _, x := range keys {
		if parent[x] == x {
			best = max(best, size[x])
		}
	}
	return best
}

var longestConsecutive = function(nums) {
    const parent = new Map(), size = new Map();
    for (const x of nums) {
        parent.set(x, x);
        size.set(x, 1);
    }
    const find = (x) => {
        let root = x;
        while (parent.get(root) !== root) root = parent.get(root);
        while (parent.get(x) !== root) {
            const next = parent.get(x);
            parent.set(x, root);
            x = next;
        }
        return root;
    };
    const keys = [...parent.keys()];
    for (const x of keys) {
        if (!parent.has(x + 1)) continue;
        let a = find(x), b = find(x + 1);
        if (a === b) continue;
        if (size.get(a) < size.get(b)) [a, b] = [b, a];
        parent.set(b, a);
        size.set(a, size.get(a) + size.get(b));
    }
    let best = 0;
    for (const x of keys) {
        if (parent.get(x) === x) best = Math.max(best, size.get(x));
    }
    return best;
};

function longestConsecutive(nums: number[]): number {
    const parent = new Map<number, number>(), size = new Map<number, number>();
    for (const x of nums) {
        parent.set(x, x);
        size.set(x, 1);
    }
    const find = (x: number): number => {
        let root = x;
        while (parent.get(root)! !== root) root = parent.get(root)!;
        while (parent.get(x)! !== root) {
            const next = parent.get(x)!;
            parent.set(x, root);
            x = next;
        }
        return root;
    };
    const keys = [...parent.keys()];
    for (const x of keys) {
        if (!parent.has(x + 1)) continue;
        let a = find(x), b = find(x + 1);
        if (a === b) continue;
        if (size.get(a)! < size.get(b)!) [a, b] = [b, a];
        parent.set(b, a);
        size.set(a, size.get(a)! + size.get(b)!);
    }
    let best = 0;
    for (const x of keys) {
        if (parent.get(x) === x) best = Math.max(best, size.get(x)!);
    }
    return best;
}

哈希表专题的其他题目

查看哈希表全部题目 →