思路1：hash ——>时间复杂度O(n)
定义一个flag变量，下标只能是非负数，看到nums[i]的取值范围，放弃了。。。
技巧： hash 可以用unordered_map啊
分析题目：不需要键->值，只要保存存在的那些值就可以了，所以可以考虑set来节省存储空间
题目需要去重+hash+不需要映射 ——>unorderes_set

class Solution {
public:int longestConsecutive(vector<int>& nums) {//如果当前元素不是第一个元素（前一个在hash中）cnt++，否则cnt = 0;unordered_set<int> s;int n = nums.size();for (int i = 0; i < n; ++i) {s.insert(nums[i]);}int ans = 0;for (int i = 0; i < n; ++i) {int cnt = 0;int each = nums[i];if (!s.count(each - 1)) {while (s.count(each)) {cnt++;each++;}}ans = max(ans, cnt);}return ans;}
};

思路2：区间合并 ——>时间复杂度O(nlogn)
思路： 先得到大于该值的一个区间1（左端点大于该值），然后得到该区间左边的一个区间2，如果该值小于等于区间2的右端点则不处理，否则讨论：区间1 该值 区间2三者之间的关系。
易错点+技巧
1：为了不讨论边界，设置两个边界数组
2：set 和map的upper_bound()都是一个参数！！！
3：map 用insert(存在的键)会插入失败 用[存在的键]会覆盖之前的！！！

class Solution {
public:int longestConsecutive(vector<int>& nums) {//区间合并map<int, int> mp;mp.insert(make_pair(-1e9 - 2, -1e9 - 2)); //为了不讨论边界，设置两个边界数组mp.insert(make_pair(1e9 + 2, 1e9 + 2));int ans = 0, n = nums.size();for (int i = 0; i < n; ++i) {auto greater = mp.upper_bound(nums[i]); //upper_bound()是一个参数！！！auto small_equ = greater; small_equ--; //得到左边第一个区间if (nums[i] <= small_equ->second) {continue;}else { if ((nums[i] == small_equ->second + 1) && (nums[i] == greater->first - 1)) {//mp.insert(make_pair(small_equ->first, greater->second)); 不行！！！mp[small_equ->first] = greater->second;mp.erase(greater);}else if (nums[i] == small_equ->second + 1) {//mp.insert(make_pair(small_equ->first, small_equ->second + 1));不行！！！mp[small_equ->first] = small_equ->second + 1;}else if (nums[i] == greater->first - 1) {mp.insert(make_pair(greater->first - 1, greater->second));mp.erase(greater);}else {mp.insert(make_pair(nums[i], nums[i]));}}}if (!n) return 0;for (auto &m: mp) {ans = max(ans, (m.second - m.first + 1));}return ans;}
};

思路2：并查集 ——>查找合并近似O(1)，因此总时间复杂度O(n)
并查集只能定义数组的样子，不能处理负数？放弃了。。。
技巧： father数组 可以用unordered_map啊
father数组中存的是较大的值，因此 union(较小值， 较大值)

class Solution {
public:unordered_map<int, int> father;int findfather(int u);int longestConsecutive(vector<int>& nums) {//并查集int n = nums.size();for (int i = 0; i < n; ++i) {father[nums[i]] = nums[i];}for (auto &m : father) { //不能遍历nums数组，因为可能存在重复数字if (father.count(m.first - 1)) {int fau = findfather(m.first - 1);int fav = m.first;father[fau] = fav;}}int ans = 0;for (auto &m : father) {ans = max(ans, findfather(m.first) - m.first + 1);}return ans;}
};
int Solution::findfather(int u) {if (u == father[u]) return u;return father[u] = findfather(father[u]); 
}