最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

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

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：

输入：nums = [1,0,1,2]
输出：3

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

哈希-去重-连续：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {

        unordered_set<int> st;

        for (int num : nums) {
            st.insert(num);
        }

        int ans = 0;

        for (int num : st) {

            if (st.find(num - 1) == st.end()) {

                int cur = num;
                int len = 1;

                while (st.find(cur + 1) != st.end()) {
                    cur++;
                    len++;
                }

                ans = max(ans, len);
            }
        }

        return ans;
    }
};

首先这题目要求在O(n)的时间范围，那么基本上就是哈希了。像计数排序之类的，条件都卡的比较死，不太具有普遍意义。然后首先将原数组元素全部加入哈希集合中，这里要注意不要使用键可重复的容器类型。

然后是关于最长连续序列长度的求解问题 。首先虽然数组元素填入哈希集合的时候，没有经过排序。但是我们要求的序列在数值上有着连续性，也就是说我们可以利用哈希的特性，找到一个连续序列的起始位置，然后定长递增，直到找不到新的元素为止。

这里要思考的点只有一个，那就是怎么找到一个序列的起始位置。这同样要用到题目中的连续条件，即：既然一个序列连续，那么当一个数不是序列的起始位置时，它的前面一定还有一个相邻的数。那么反之，如果这个数前面没有相邻的数，那就说明它就是序列的起始位置。而在当前指向的数字不是序列起始数时，我们就不进行访问。反之，我们就不断去找这个序列的下一个数，直到结束为止，然后统计长度，和之前记录的连续序列最大值进行比较，选出新的最大值。

然后是为什么这个算法是O(n)的。有些人可能会说：你看，外部for循环是整个数组的遍历，然后内部还有个while循环，如果整个数组都是连续的也有可能遍历整个数组。那么外循环最高是O(n)，内循环也是O(n)。嵌套一下，不应该是O(n²)吗？这里我们就要注意到while循环里面的语句是总共执行n次，它的状态是不会刷新的，不是每次循环它都可能执行n次。举个例子：1，2，3；5，6，7。这时，while循环语句只会在遍历到1和5的时候触发。在2，3，6，7的时候是不会进入while循环的。

接下来解释为什么不能使用键可重复的容器类型。因为，题目给的样本数据很可能有非常多的重复数据，那么如果这些重复数据大部分都是连续序列的起始位置的话，while循环就不是总共执行n次了，最坏的情况会达到O(n²)。这样就会浪费大量时间，从而导致过不了。同样的，为了避免这个情况，我们第二次for循环，不能和第一个for循环一样遍历题目给出的数组，需要遍历我们自己获得的哈希集合。因为键不可重复，所以哈希集合中的数据都是去过重的。