[LeetCode]128. Longest Consecutive Sequence

Problem

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

Your algorithm should run in O(n) complexity.

Example:

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

给定一个整数无序数组, 返回最长连续序列.

要求时间复杂度为O(n).

Solution

Analysis

无序数组,而且要求时间复杂度为O(N). 所以限制了不能使用排序+双指针法.

这里使用hash表方法. 首先,需要明白的一点是, 比如[1,2,3], 无论当前数是从1开始,还是2,3,最长连续序列长度都是3. 此外还有一点非常重要,题目并不要求序列中的数字在位置上是连续的, 可以是原数组的一个子集. 所以,我们可以在hash表中,以当前元素为中心,双指针向两端扩散, 如果元素存在,扩散,连续长度增加. 然后,记录最大值. 遍历结束,返回最大长度. 另外,要避免重复性工作, 比如[1,2,3]从1开始查找后, 之后就没有必要再从2/3重复查找了, 因为它们是连续的,得出的长度一定是相同的.

Code

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        
        unordered_map<int, bool> tabel;
        // 建立hash表
        for(auto num: nums) tabel[num] = false;
        
        int longest = 0;// 照顾空数组
        
        for (auto i: nums){//[100,4,200,1,3,2]: 查找4时,1,2,3都会找到,下次遍历时,直接跳过
            if (tabel[i]) continue;// 跳过重复计算部分
            
            int length = 1;
            
            tabel[i] = true;
            
            for (int j=i+1; tabel.find(j) != tabel.end(); j++){
                length++;
                tabel[j] = true;
            }
            for (int j=i-1; tabel.find(j) != tabel.end(); j--){
                length++;
                tabel[j] = true;
            }
            
            longest = max(longest, length);
        }
        
        return longest;
    }
};

Problem

Solution

Analysis

Code

推荐文章（由hexo文章推荐插件驱动）