LeetCode 128. 最长连续序列

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 128. 最长连续序列

思路分析

这个问题的关键在于如何在 O(n) 时间内找到最长连续序列。我们可以使用 HashSet 来实现这一目标，具体思路如下：

创建一个 HashSet，将数组中的所有元素存储到 HashSet 中。

遍历数组中的每个元素，对于每个元素 num，判断 num - 1 是否存在于 HashSet 中。如果不存在，说明 num 是一个连续序列的起点。

对于每个连续序列的起点 num，开始递增 num，同时检查 num + 1 是否存在于 HashSet 中，以此来扩展连续序列的长度。

在遍历过程中，不断更新最长连续序列的长度。

返回最长连续序列的长度作为结果。

参考代码

func longestConsecutive(nums []int) int {
	numSet := make(map[int]bool)
	for _, num := range nums {
		numSet[num] = true
	}
	maxLength := 0
	for num := range numSet {
		if !numSet[num-1] { // 如果 num 是序列的起点
			curNum := num
			curLength := 1
			// 依次检查序列中的下一个数字
			for numSet[curNum+1] {
				curNum++
				curLength++
			}
			// 更新最大长度
			if curLength > maxLength {
				maxLength = curLength
			}
		}
	}
	return maxLength
}

🍏 点击查看 Java 题解

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

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/54759261