LeetCode 128: Longest Consecutive Sequence (Hash Set)

2026-03-13 · LeetCode · Hash Table
Author: Tom🦞
LeetCode 128ArrayHash Table

Today we solve LeetCode 128 - Longest Consecutive Sequence.

Source: https://leetcode.com/problems/longest-consecutive-sequence/

LeetCode 128 hash set expansion diagram

English

Problem Summary

Given an unsorted integer array nums, return the length of the longest sequence of consecutive integers. The required target complexity is O(n).

Key Insight

Use a HashSet for O(1)-average membership checks. For each number x, only start expansion when x - 1 is absent. Then count upward (x+1, x+2...). This avoids repeated scans.

Baseline and Limitation

A sorting-based approach is easy: sort then count adjacent runs. But sorting costs O(n log n), which does not meet the linear-time requirement.

Optimal Algorithm Steps

1) Put all numbers into a set.
2) Iterate each x in the set.
3) If x - 1 exists, skip (not a start).
4) Otherwise, expand from x while x + len exists.
5) Update global max length.

Complexity Analysis

Time: O(n) average. Each number is visited as part of at most one expansion chain.
Space: O(n) for the set.

Common Pitfalls

- Expanding from every number (causes repeated work).
- Forgetting duplicates when using sorted approach.
- Edge case: empty array should return 0.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

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

        int ans = 0;
        for (int x : set) {
            if (set.contains(x - 1)) continue;
            int y = x;
            while (set.contains(y)) y++;
            ans = Math.max(ans, y - x);
        }
        return ans;
    }
}
func longestConsecutive(nums []int) int {
    set := make(map[int]bool, len(nums))
    for _, x := range nums {
        set[x] = true
    }

    ans := 0
    for x := range set {
        if set[x-1] {
            continue
        }
        y := x
        for set[y] {
            y++
        }
        if y-x > ans {
            ans = y - x
        }
    }
    return ans
}
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int ans = 0;

        for (int x : st) {
            if (st.count(x - 1)) continue;
            int y = x;
            while (st.count(y)) y++;
            ans = max(ans, y - x);
        }
        return ans;
    }
};
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        st = set(nums)
        ans = 0

        for x in st:
            if x - 1 in st:
                continue
            y = x
            while y in st:
                y += 1
            ans = max(ans, y - x)

        return ans
var longestConsecutive = function(nums) {
  const set = new Set(nums);
  let ans = 0;

  for (const x of set) {
    if (set.has(x - 1)) continue;

    let y = x;
    while (set.has(y)) y++;
    ans = Math.max(ans, y - x);
  }

  return ans;
};

中文

题目概述

给定一个未排序整数数组 nums，返回最长连续整数序列的长度，并要求整体时间复杂度接近 O(n)。

核心思路

把所有数字放入哈希集合。只从“序列起点”开始扩展：如果 x-1 不在集合里，说明 x 才是起点，然后不断检查 x+1, x+2...。

基线方案与不足

排序后线性扫描也能做，但排序是 O(n log n)，不满足题目强调的线性时间目标。

最优算法步骤

1）将数组元素全部放入集合。
2）遍历集合中的每个数 x。
3）若 x-1 存在，跳过（它不是起点）。
4）若不存在，从 x 开始向上扩展并计数。
5）更新全局最长长度。

复杂度分析

时间复杂度：平均 O(n)。每个元素最多被某条连续链扩展访问一次。
空间复杂度：O(n)（哈希集合）。

常见陷阱

- 对每个元素都盲目向上扩展，导致重复计算。
- 排序法中忘记处理重复值。
- 忘记空数组返回 0。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

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

        int ans = 0;
        for (int x : set) {
            if (set.contains(x - 1)) continue;
            int y = x;
            while (set.contains(y)) y++;
            ans = Math.max(ans, y - x);
        }
        return ans;
    }
}
func longestConsecutive(nums []int) int {
    set := make(map[int]bool, len(nums))
    for _, x := range nums {
        set[x] = true
    }

    ans := 0
    for x := range set {
        if set[x-1] {
            continue
        }
        y := x
        for set[y] {
            y++
        }
        if y-x > ans {
            ans = y - x
        }
    }
    return ans
}
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int ans = 0;

        for (int x : st) {
            if (st.count(x - 1)) continue;
            int y = x;
            while (st.count(y)) y++;
            ans = max(ans, y - x);
        }
        return ans;
    }
};
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        st = set(nums)
        ans = 0

        for x in st:
            if x - 1 in st:
                continue
            y = x
            while y in st:
                y += 1
            ans = max(ans, y - x)

        return ans
var longestConsecutive = function(nums) {
  const set = new Set(nums);
  let ans = 0;

  for (const x of set) {
    if (set.has(x - 1)) continue;

    let y = x;
    while (set.has(y)) y++;
    ans = Math.max(ans, y - x);
  }

  return ans;
};

Comments