128. Longest Consecutive Sequence

June 6, 2021 - 1 minutes read - 297 words

Leetcode 128. Longest Consecutive Sequence

題目

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.

想法

這題是要從一堆沒有規則並且可能會重複數字中，找最長的連續數字串的長度。

因為 Set 有不重複的特性，可以用來處理重複的問題，而且找指定數字時只要 O(1) 時間，所以我們用 Set 來做。

做法很單純，遍歷 nums set，我們只從每一串最小數字開始找起，串中數字就跳過，因為必定會算過，不必重複算。

實作

Javascript

var longestConsecutive = function(nums) {
    // max 存最大長度
	let max = 0;

    // 用 Set 來去重複，且找指定數字時只要 O(1)
	const nums_set = new Set(nums);

	for(let num of nums_set) {
        // 如果 Set 中有比這個 num 小的，代表我們已經找過這串了，跳過
		if(nums_set.has(num-1)) continue;
        
        // 新的串包含自己
        let count = 1;

        // 一直網上找，直到斷掉
        while(nums_set.has(++num)) count++;
        
        // 試著更新最大長度
        max = count > max ? count : max;
    }

    // 回傳最大長度
	return max;
};