LeetCode-128. 最长连续序列

川长思鸟来 2022-02-20 16:35 214阅读 0赞

# [128. 最长连续序列][128.] #

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
    输出: 4
    解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

### hash 数组 ###

> 用哈希表存储每个端点值对应连续区间的长度  
> 若数已在哈希表中：跳过不做处理  
> 若是新数加入：  
> 取出其左右相邻数已有的连续区间长度 left 和 right  
> 计算当前数的区间长度为：cur\_length = left + right + 1  
> 根据 cur\_length 更新最大长度 max\_length 的值  
> 更新区间两端点的长度值

class Solution { 
    public:
        int longestConsecutive(vector<int>& nums) { 
            if(nums.size()==0) return 0;
            unordered_map<int,int> mp;
            int ans=0;
            for(int i=0;i<nums.size();i++)
            { 
                int left=0;
                int right=0;
                if(mp.find(nums[i])!=mp.end()) continue;
                if(mp.find(nums[i]-1)!=mp.end())
                { 
                    left=mp[nums[i]-1];
                }
                if(mp.find(nums[i]+1)!=mp.end())
                { 
                    right=mp[nums[i]+1];
                }
                int count=left+right+1;
                mp[nums[i]]=count;
                if(left)
                { 
                    mp[nums[i]-left]=count;
                }
                if(right)
                { 
                    mp[nums[i]+right]=count;
                }
                ans=max(ans,count);
            }
            return ans;
        }
    };

[128.]: https://leetcode-cn.com/problems/longest-consecutive-sequence/