题目

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

1
2
3

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

题解

这道题要求实现复杂度为O(N)，因此一开始也就往这个复杂度去想，既然是O(N)，那么肯定遍历一次就够，如果想得知连续这个状态，必须要将一些中间数据存储下来。因为数据的大小未知，所以不能通过数组记录中间状态，要通过map。

后来仔细想了下，有了大致的思路，但实现起来的复杂度并不是O(N)，所以很纠结。以[100, 4, 200, 1, 3, 2]为例，思路大致如下：

定义map为dp，遍历整个数组，首先我们得到100，这样dp[100]等于dp[99] + 1 + dp[101]，即dp[i] = dp[i - 1] + 1 + dp[i + 1]。由于dp[99]和dp[101]都不存在，默认为0，所以dp[100]为1。

接下来得到4，同样dp[4] = 1 + dp[3] + dp[5]，dp[4]还等于1。之后是200，结果依旧为1。接下来是1，结果依旧为1。再然后是3，这个时候就得注意了，dp[3] = 1 + dp[2] + dp[4]，其中dp[4]为1，那么dp[3]为2。再之后是2，dp[2] = 1 + dp[1] + dp[3]，便是1 + 1 + 2 = 4。

具体的内存图如下：

1 2 3 4 100 200
1 4 2 1 1 1

虽然上述算法得出了结果，但存在一个问题，如果数组最后还有一个5，那么dp[5] = dp[4] + 1 + dp[6]，这样计算出的结果为2，显然是不对的。因此我们在上述计算过程中需要将结果蔓延至边界。也即当我们计算出dp[2]的结果时，我们要往两边蔓延，将dp[1]的结果改为4，将dp[4]的结果也改为4。这样再来一个5时就不会有问题了。

但加了这个蔓延操作后，显然复杂度就不是O(N)了，下面是自己的实现，提交后果然超时。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int longestConsecutive(vector<int>& nums) {
   int max_len = 0;
   unordered_map<int, int> m;

   for (auto &itr : nums) {
       if(m[itr] == 0)
           m[itr] = 1 + m[itr - 1] + m[itr + 1];

       int i = 1;
       while (m[itr - i] != 0) {
           m[itr - i] = m[itr];
           i++;
       }
       
       i = 1;
       while (m[itr + i] != 0) {
           m[itr + i] = m[itr];
           i++;
       }
           
       max_len = max(m[itr], max_len);
   }

   return max_len;
}

以上提交超时，看了下相关的讨论，果然是有强人的。我在实现蔓延操作时，使用的是遍历，但实际上不需要这样，两边结果中存储的数就是我们要蔓延的目的地。当计算完dp[2]之后，我们要进行蔓延操作，这个时候看dp[3] = 2，那么dp[2 + 2]既是我们要修改的边界。dp[1] = 1，那么dp[2 - 1]既是我们要修改的边界。

我们在进行上述计算时，实际上是已经把当前值到边界的值存储了两边的dp结果中了。因此不用像我那样进行循环查找边界，实现了O(N)的时间复杂度，对应的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int longestConsecutive(vector<int>& nums) {
    unordered_map<int, int> dp;
    int ret = 0;
    for (auto &x : nums) {
        if (!dp[x]) {
            int value = dp[x - 1] + dp[x + 1] + 1;
            dp[x] = value;
            dp[x - dp[x - 1]] = value;
            dp[x + dp[x + 1]] = value;
        }
        ret = max(ret, dp[x]);
    }

    return ret;
}

另外，从讨论中还看到了一种基于hash表的实现，实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> st;
    for (int n : nums) st.insert(n);
    int ans = 0;
    for (int i : st) {
        // 假如一个数在哈希表中存在比他小的，那么它不是可以作为开头的数字
        if (i != INT_MIN && st.count(i - 1)) {
            continue;
        }
        int cnt = 1;
        while (i != INT_MAX && st.count(i + 1)) {
            cnt++;
            i++;
        }
        ans = max(ans, cnt);
    }
    return ans;
}

大致思想是，首先对所有的数字去重，之后遍历去重后的数字，通过hash表找到连续的最小数字，之后由这个最小的数字往后循环，找到连续的最大数字。