leetcode之最长连续子序列

大学生每天刷leetcode要坚持下去是怎么回事呢？大学生相信大家都很熟悉，但是大学生每天刷leetcode要坚持下去是怎么回事呢，下面就让小编带大家一起了解吧。大学生每天刷leetcode要坚持下去，其实就是刷力扣对提高思维能力很有帮助，大家可能会很惊讶大学生怎么会每天刷leetcode要坚持下去呢？但事实就是这样，小编也感到非常惊讶。

今天小编会带来一条什么题目呢？？现在就给大家揭晓题目如下～～

先审题～～

发现这个题目其实很好理解～～题如其名，就是要在乱序的数组里找到最长连续子序列～～～

这题虽然被标注为HARD，但是小编完全不再怕的～～ hard的原因是题目中要求复杂度必须要在O（n)以内，小编现在和大家一起扩展思路~

假如没有复杂度的限制，而仅仅如题目中所说只要找出最长连续子序列，该怎么做呢？？？

思路一：

暴力解法：对每个数都寻找他接下来的连续的数，然后再一起比较谁最长，这样子的复杂度是O（n^3),显然是太复杂了～～～

思路二：

排序法：先将数组排序再进行子序列长度的度量，选择最长的。酱紫排序的复杂度为O（lgn),总体的复杂度就是O（nlgn),看起来还好～～但是还有很多提升空间，一定要加油哦！！排序法的C代码如下：

#include

int compare(const void* a, const void* b)

{

return *((unsigned int*)a) - *((unsigned int*)b);

}

//以上这个compare函数主要是为了C语言里面的qsort函数啦～～具体想了解这个qsort函数的函数的话呢，小编这里建议百度啦～～～这里面的a,b都采用了（unsigned int*)主要是为了表达位数比int更加多～～～

int longestConsecutive(int* num, int numSize)

{

  while(numSize != 0 ){   

//这是要判断数组是不是[ ]也就是里面什么都没有～～，区别于[0]哦！

qsort(num, numSize, sizeof(int), compare);

//这个函数就是C语言里面的 qsort啦！

int max = 0, temp = 1;

for(int i = 1; i

{

  if(num[i] == num[i-1])  continue;//一样的值就不管他，跳出本次for循环但是temp的值依然记录着～～

  if(num[i] == num[i-1]+1)

    temp++;

 else

  {

    max = (max> temp)?max:temp;

    temp = 1;//一旦途中的连续值断了，这里必须要重置temp的值哦！！！！

  }

}

return (max> temp)?max:temp;//最终输出～～

}

return 0;//数组是[ ]的话，输出是0哦～～～

}

好了，以上就是排序法的所有代码了！！小编也非常开心，因为排序法非常好理解，但是复杂度还不够要求，接下来小编就带来本题的最终解法！！

思路三：

哈希表～～哈希表和线性空间的构造（其实可以被看作是思路一暴力法的优化啦！！）

HashMap中的key表示读到的数组中每个元素的值，value对应的是数组中每个key所处的连续序列的长度!

遍历数组nums[i]的时候将数组中每一个元素插入到HashMap去，可能出现以下几种情况：

（1）插入HashMap中该元素已经被插入过，则不插入。

（2）插入HashMap中该元素没有被插入过且该元素没有相邻的元素，则令key=nums[i],value=1，插入到HashMap中去即可。

（3）插入HashMap中某元素key=3时，有比它大的相邻的元素，则一直遍历找到与它相邻序列中最大的那个元素，然后将连续序列的首尾key对应的value更新为连续序列的长度。

key      3    4    5

value   3     2    3

（4）插入HashMap中某元素key=7时，有比它小的且相邻的元素，则一直遍历HashMap找到与它相邻序列中最小的那个元素，然后将连续序列首尾的Key对应的value更新为最新的连续序列的长度个数。

key      5    6    7

value   3     2    3

（5）插入HashMap中某元素key=5时，有比它大的相邻的元素，也有比它小的相邻的元素的时候，我们先遍历HashMap找到与它相邻且比它大的序列中最大的那个元素，然后将连续序列的首尾key对应的value更新为最新的连续序列的长度；然后遍历HashMap找到与它相邻且比它小的序列中最小的那个元素，然后将最长的连续序列的首尾的Key对应的value更新为序列的长度。

key      3   4    5    6    7

value   5    2    3    2    5

以上就是哈希表的构造方法了！是不是很神奇呢！！！小编也很惊讶于程序员的智慧！！！

接下来就是代码实现了～～～～～～

struct mystruct{

  int number;

  UT_hash_handle hh;

};

struct mystruct *t;

struct mystruct *find(int number) {

  struct mystruct *s;

  HASH_FIND_INT(t, &number, s);

  return s;

}//定义了结构体相关，小编这里不想展开写了，有问题评论区见吧～～～

void add(int num){

  struct mystruct *s = (struct mystruct *)malloc(sizeof(struct mystruct));

  if(find(num) == NULL){//没被插入的key就存入～

      s->number = num;

      HASH_ADD_INT(t, number, s); 

  } 

}

int longestConsecutive(int* nums, int numSize){

  t = NULL;

  int max = 0;

  if(numSize == 0)

      return numSize;

  for(int i = 0; i < numSize; i++){

      add(nums[i]);

  }

  for(int i = 0; i < numSize; i++){

      if(find(nums[i] + 1) == NULL){

          int tmp, n;//tmp用来保存比该元素大的且连续的最大的那个元素

          n = nums[i];

          tmp = n;

          while(find(n)){

              n -= 1;

          }                                           

          max = ((tmp - n) > max) ? (tmp - n) : max;

      }

  }   

  return max;

}

好了～～小编写到这里就已经很困啦～～

先晚安啦～～～