做网站去哪找客户/农产品网络营销

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

这个题乍一看要动态规划，其实不能用，因为他没有可以推导的关系式。
其实最开始想到的就是先排序，然后从左往右遍历，
比如用下面这个代码，如果没有排序后去重这一步，就会导致错误，因为比如0 1 1 2 。在到第二个1的时候cnt重新置1了。当然我们可以改成这样,对是否是重复的进行判断。但是去重是一个值得考虑的事。
while((i+1<n&&nums[i+1]-nums[i]==1)||(i+1<n&&nums[i+1]==nums[i]))
{
if(nums[i+1]-nums[i]==1)
{
cnt++;
i++;
}
else
i++;
}

sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());//unique()函数将相邻且重复的元素放到vector的尾部 然后返回指向第一个重复元素的迭代器再用erase函数擦除从这个元素到最后元素的所有的元素。这种方法居然最优   明天了解下mapset等各种用法和复杂度int n=nums.size();if(nums.size()==0){return 0;}if(nums.size()==1){return 1;}int ans=1;int i=0;while(i+1<n){int cnt=1;while(i+1<n&&nums[i+1]-nums[i]==1){cnt++;i++;}i++;ans=max(ans,cnt);}return ans

unique()函数将相邻且重复的元素放到vector的尾部 然后返回指向第一个重复元素的迭代器再用erase函数擦除从这个元素到最后元素的所有的元素
如果用sort+unique去重，那么复杂度至少是nlogn+n平方。因为erase的操作是线性复杂度的。

那么，如果用哈希表（map）来将元素存储，键代表nums的值，因为键的唯一性，那么自然也就去重了，而且map是有序的，从begin开始遍历就是有序的，这样只要用nlogn复杂度就够了，Map的插入查询都是logn，如果用unoedered_map的话就是线性复杂度了，但是它是无序的无法满足条件。
如下

**在这里插入代码片**
map<int,bool> hash; //这里体现了Map和unordered_map区别，map插入后数据有序的底层是红黑树，unordered底层是哈希表，也就是begin就是原来的第一个元素for(int i=0;i<n;i++){hash[nums[i]]=true;}vector<int> num;for(auto it = hash.begin();it!=hash.end();it++){if(it->second==true){num.push_back(it->first);}}int m=num.size();//sort(num.begin(),num.end());int ans=1;int i=0;while(i+1<m){int cnt=1;while(i+1<m&&num[i+1]-num[i]==1){cnt++;i++;}i++;ans=max(ans,cnt);}return ans;

但是，如果题目就是让你去重，并不要排序，就可以使用unordered_map，这样的话平方复杂度的去重就变成线性复杂度了。

另外还有一个点就是，在这题中，用sort比用map会快很多，原因是，map的缺点是如果元素范围很大，那么遍历一遍就需要很久，所以map适用于那么元素数量很多但是范围不大的去重。