题目链接：Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,

Given [100, 4, 200, 1, 3, 2],

The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

这道题的要求是在数组中找到最长连续子序列。

  1. 排序

先排序，再去重，然后统计最长连续字串即可。不过这样时间复杂度主要是排序时的O(nlong)，高于要求的O(n)，不过仍然可以AC。

时间复杂度：O(nlogn)

空间复杂度：O(1)

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> &num)
    {
        sort(num.begin(), num.end());
        unique(num.begin(), num.end());
        
        int res = 0, cur = 1;
        for(int i = 1; i < num.size(); ++ i)
            if(num[i] - num[i - 1] == 1)
                ++ cur;
            else
            {
                res = max(res, cur);
                cur = 1;
            }
        res = max(res, cur);
        
        return res;
    }
};

  1. 建Hash

要求时间复杂度O(n)，可以考虑从num数组中的某一个数字开始，往两侧依次查看连续数字是否在num中。因此，先用set存储所有数字，然后从set的第一个元素开始，逐个查看两边元素是否在set中，如果在，cur计数器加1，同时在set中删除该数字。这样，建set时复杂度O(n)，然后只是遍历了一遍set中的元素，时间复杂度还是O(n)，因此总的时间复杂度为O(n)。

不过，这O(n)复杂度的思路还没有上面先排序的思路快，看来STL的sort速度可以啊。。。

时间复杂度：O(n)

空间复杂度：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

class Solution
{
public:
    int longestConsecutive(vector<int> &num)
    {
        unordered_set<int> set(num.begin(), num.end());
        
        int res = 0;
        while(!set.empty())
        {
            auto it = set.begin();
            int a = *it, cur = 1;
            set.erase(it);
            
            for(int i = a - 1; set.find(i) != set.end(); ++ cur, -- i)
                set.erase(i);
            for(int i = a + 1; set.find(i) != set.end(); ++ cur, ++ i)
                set.erase(i);
            
            res = max(res, cur);
        }
        return res;
    }
};