本文共 1078 字，大约阅读时间需要 3 分钟。

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.

解答：

哈希 空间换时间

代码：

class Solution {public:    map
   
     mp;    int longestConsecutive(vector
    
      &num) {        int i, j;        for(i = 0; i < num.size(); i++)            mp[num[i]] = 1;        int max = 0;        for(i = 0; i < num.size(); i++)        {            int sum = 1;            if(mp.count(num[i])){                mp[num[i]] = 0;                int left = num[i] -1;                while(mp.count(left) && mp[left] != 0)                {                    mp[left--] = 0;                    sum++;                }                int right = num[i] + 1;                while(mp.count(right) && mp[right] != 0){                    mp[right++] = 0;                    sum++;                }            }            if(max < sum)                max = sum;        }        return max;    }};
    
   

转载地址：http://yutsi.baihongyu.com/