【letcod-c++】128.最长连续序列
一、题目
二、分析
第一想法是像“242字母异位词”那样用哈希数组，但是这个数组元素的范围比较广，元素又比较分散，用数组太浪费空间，不合适。
于是考虑用哈希set(unordered_set),这个时候忽然想到前几天学习到set它能自动排序且自动去重，非常合适用到这一题中。
set、mulltiset、unordered_set的区别：unordered_set: 底层是哈希，所以顺序是乱的由哈希函数决定，但查找效率高multiset和set：底层都是红黑树，插入时自动排序（默认按从小到大，也可以通过仿函数指定排序规则），适用于有序操作。这两个的区别是set自动去重，而multiset允许出现重复元素。
那么这一题如果能够元素排好序只需要通过前后两个元素的差值是否为1就可以判断是否连续，而且根据第二个例子，出现重复的元素时只能算一个，所以需要去重，那么综合来说，set容器是最合适的。
三、代码
class Solution {
public:
/*
set: 自动排序且自动去重
1.先遍历一遍把数组元素塞到set容器中，就可以得到一个从小到大排序且数字不重复出现的序列
2.遍历这个set序列，判断当前元素和她的前一个元素是不是相差1，是则连续，计数增加；不是则断开，保存最大值并计数归0
这样遍历一轮就可以得到最大值了。
*/int longestConsecutive(vector<int>& nums) {if(nums.size()==0) return 0;if(nums.size()==1) return 1;set<int> nums_new;for(int i=0;i<nums.size();i++){nums_new.insert(nums[i]);}//长度至少也是个1int maxLen=1;int currentLen=1;set<int>::iterator it=nums_new.begin();int leftnum=*it;it++;for(;it!=nums_new.end();it++){if(((*it)-leftnum)==1){currentLen++;}else{if(currentLen>maxLen) maxLen=currentLen;currentLen=1;}leftnum=*it;}if(currentLen>maxLen) maxLen=currentLen;return maxLen;}
};