Leetcode：128. 最长连续序列

128. 最长连续序列

乍一看感觉很简单，一看要用O(n)???
因为我觉得题目很难而且题目看起来很简单，感觉以后会用到😆，做个记录

1.朴素做法

• 思路
  答:任何一段连续的数都有一个左端点：比如（1，2，3，4）的左端点是1，且找到1之后，发现（1，2，3，4）为最长的连续区间，那么从2，3，4为左端点的区间都不需要继续尝试了，因为他们都比1为左端点的区间短。
  那么我们只需要找所有的左端点，然后不停比较更新即可。
  • 怎么找左端点？只要没有比它更小的数，那么就是左端点：比如[100,1,3,2,4],这个数组有两个左端点：100，1。
  • 用哈希表空间换时间，这样就不需要每次找到一个数，然后去for循环判断有没有比他小的数以及他后面接着几个连续的数

class Solution 
{
public:
    int longestConsecutive(vector<int>& nums) 
    {
		int n=nums.size();
		unordered_set<int>Hash;  //set只有一个参数，然后去重，重复的键值不会被插入
		for(int i=0;i<n;i++)
			Hash.insert(nums[i]);
		int ans=0;
		for(int i=0;i<n;i++)
		{
			if(Hash.find(nums[i]-1)!=Hash.end())//num[i]-1存在，nums[i]不是左端点
				continue;
			else
			{
				int x=nums[i]+1;  //nums[i]是左端点，从x开始尝试找
				int len=1;
				while(Hash.find(x)!=Hash.end())
				{
					x++;
					len++;
				}
				ans=max(ans,len);
			}
		}
		return ans;
    }
};

2.并查集

• 思路
  将连接在一起的数放在一个集合，且这个集合的根节点是当前集合最大的数
  • 这里也用到左端点的思路，而且优化了并查集，一步到位。

class Solution {
public:
    unordered_map<int,int> a;
    int find(int x)   //找到该元素集合的根节点+路径压缩
    {
        if(a.count(x))
        {
            a[x]=find(a[x]);
            return a[x];
        }
        else
            return x;
        //return a.count(x)?a[x]=find(a[x]):x;
    }
    int longestConsecutive(vector<int>& nums) 
    {
        for(auto i:nums)  //这一步很巧妙，这个错位的赋值使find函数一步到位，只要使连续的，那么就把所有连续的数都放在集合里了。
            a[i]=i+1;
        int ans=0;
        for(auto i:nums)
        {
            int y=find(i+1);
            ans=max(ans,y-i);
        }
        return ans;
    }
};

3.动态规划

• 思路：
  最终求的是最长的连续数组，那么可以把解分解成：左连续区间+当前元素+右连续区间，这很明显是符合逻辑的。那么把解拆分成这个形式，那么就去尝试迭代这个公式。
  • 迭代过程中，连续数组的长度是从1开始递增的，且每次迭代都会更新一段数组的左右端点，比如： 1 2 3 4 6 7 8，遍历到5，那么Hash[5]=4+1+3,Hash[1]=8,Hash[8]=8;

class Solution 
{
public:
    int longestConsecutive(vector<int>& nums)
    {
        unordered_map<int , int>Hash;
        int res = 0;
        for(int i = 0; i < nums.size(); i++) 
        {
            int now = nums[i];
            if(!Hash[now]) 
            {
                int left = Hash[now - 1] , right = Hash[now + 1];
                int len = left + right + 1;
                res = max(res , len);
                Hash[now] = len;
                Hash[now - left] = len , Hash[now + right] = len;
            }
        }

        return res;
    }
};