给定一个未排序的整数数组 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 <= 10(5)

-10(9) <= nums[i] <= 10(9)

对数组中每个元素考虑其–和++的元素是否在数组中

可以使用unordered_set us先去重，然后遍历us的每个元素 i ，再不断减一或加一判断其是否在us中，

可以只对i-1（i+1同理）不在us中的元素只判断 i++，这样同一个区间我们只需要判断一次就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestConsecutive(vector<int> &nums) {
        unordered_set<int> flag;
        int ans = 0;
        for (int i : nums)
            flag.insert(i);
        for (int i : flag) {
            int mid = i;
            if (flag.find(mid + 1) == flag.end()) {
                while (flag.find(mid) != flag.end()) {
                    mid--;
                }
                ans = max(ans, i - mid);
            }
        }
        return ans;
    }
};

也可以使用unordered_map，遍历过程中记录每个元素的最长区间值并更新，因为只有在区间边界时后续才有可能用到，所以更新时只更新左右边界即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestConsecutive(vector<int> &nums) {
        unordered_map<int, int> ans;
        unordered_map<int, bool> flag;
        int res = 0;
        for (int i : nums) {
            if (!flag[i]) {
                ans[i] = ans[i - 1] + ans[i + 1] + 1;
                int left = i - ans[i - 1];
                int right = i + ans[i + 1];

                ans[left] = ans[i];
                ans[right] = ans[i];

                res = max(res, ans[i]);
                flag[i] = true;
            }
        }
        return res;
    }
};