README_EN.md

128. Longest Consecutive Sequence

中文文档

Description

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

 

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

Solutions

1. Sort

Sort the array then compare each value. $O(n\log n)$, $O(1)$.

2. HashSet

Making use of hash set. $O(n)$, $O(n)$.

Python3

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return n
        nums.sort()
        res = t = 1
        for i in range(1, n):
            if nums[i] == nums[i - 1]:
                continue
            if nums[i] - nums[i - 1] == 1:
                t += 1
                res = max(res, t)
            else:
                t = 1
        return res

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s, res = set(nums), 0
        for num in nums:
            if num - 1 not in s:
                t, next = 1, num + 1
                while next in s:
                    t, next = t + 1, next + 1
                res = max(res, t)
        return res

Java

class Solution {
    public int longestConsecutive(int[] nums) {
        int n = nums.length;
        if (n < 1) {
            return n;
        }
        Arrays.sort(nums);
        int res = 1, t = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == nums[i - 1]) {
                continue;
            }
            if (nums[i] - nums[i - 1] == 1) {
                t += 1;
                res = Math.max(res, t);
            } else {
                t = 1;
            }
        }
        return res;
    }
}

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

C++

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        if (n < 2)
            return n;
        sort(nums.begin(), nums.end());
        int res = 1, t = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == nums[i - 1])
                continue;
            if (nums[i] - nums[i - 1] == 1) {
                ++t;
                res = max(res, t);
            } else {
                t = 1;
            }
        }
        return res;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s;
        for (int num : nums)
            s.insert(num);
        int res = 0;
        for (int num : nums) {
            if (!s.count(num - 1)) {
                int t = 1, next = num + 1;
                while (s.count(next++))
                    ++t;
                res = max(res, t);
            }
        }
        return res;
    }
};

Go

func longestConsecutive(nums []int) int {
	n := len(nums)
	if n < 2 {
		return n
	}
	sort.Ints(nums)
	res, t := 1, 1
	for i := 1; i < n; i++ {
		if nums[i] == nums[i-1] {
			continue
		}
		if nums[i]-nums[i-1] == 1 {
			t++
			res = max(res, t)
		}
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func longestConsecutive(nums []int) int {
	s := make(map[int]bool)
	for _, num := range nums {
		s[num] = true
	}
	res := 0
	for _, num := range nums {
		if !s[num-1] {
			t, next := 1, num+1
			for s[next] {
				next++
				t++
			}
			res = max(res, t)
		}
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

...