LeetCode 热题 100 -- 128、最长连续序列

OK呀码友们，今天也没有忘记继续Java的学习，持之以恒我相信一定是每一个计算机学生都具备的品质吧哈哈哈哈哈！什么？你问我昨天怎么没有更新，哈哈，只是因为我昨天没有刷算法题并不代表我没有学习哦，好了废话不多说，今天依旧是哈希相关的题目，一起看看吧。

1、分析题目

题目不长，就是给我们一个未排序的整数数组，找出最长连续序列，返回它的长度即可，特别要求了咱们设计的算法时间复杂度要是O(N)，这可能是这道题的难点所在，那么接下来分析一下，不过朋友们请注意，我不是什么算法大神，发帖子是为了教学大家最华丽最高端的算法手段，我只是一个小白，我只想记录分享一下我在写每一道算法题时的“历程”，也许我的思路能给一些同为小白的码友一些启发，不过如果觉得我的思路太菜了太业余了，也轻点喷哈，那么我们开始吧。

我最终是用了两种思路解决了这道题目。

2、第一种思路

说实话，一开始我真的一下子还一头雾水，没有什么思路，我只能剖析一下题目看看有没有什么突破口。我想到既然是要找连续的序列，给定的数组又是未排序的，那么要不试试排个序，之后通过遍历的方式解决。其实有一定的代码深度的码友肯定发现不对劲了，题目不是要求你时间复杂度O(N)吗，你调用排序后不都最少O(Nlog(N))了吗？是的没错，我承认你说的对，但是我先是想能解决了再说[嘿嘿]。排序后，我的思路是遍历nums，随后用一个HashMap存储，连续序列的开头作为key，值就是这段序列的长度。随后再遍历一遍HashMap，找出最大长度并输出。以下是我的代码实现，请各位大佬赏脸瞅瞅：

代码乍一眼看上去还是比较长的哈。我也是经历了几次报错后修修改改最终拿出的这个版本[哭]。

遍历时思路大致就是如果遍历到数组中有重复的数，要跳过（也就是去重，其实有更好的办法），随后就是记录连续序列的长度，不过要注意索引越界的条件限制（我就踩了坑的），最后存进HashMap即可。

不过虽然测试是通过的，但是其实是不符合条件的。虽然遍历部分的时间复杂度是O(N)，但是我是排了序的，排序的时间复杂度是O(Nlog(N))，所以代码的最终时间复杂度就是O(Nlog(N))，还得再想想其他算法，以下贴上提交记录。

3、第二种思路

随后我又陷入了沉思[沉默.....]。相信大家也都看出来了，排序肯定行不通，并且去重的部分也可以优化。随后就想到了Set，底层的数据结构决定了其天然去重。那么既然不能排序，那就只能通过优化遍历思路来尝试解决问题了。我们想到，如果某个数N作为一个连续序列的开头，那么对应Set里面就不会有N-1这个数的存在，并且哈希表的优点就包括查询速率快，那么可以遍历时试试直接查询集合中是否包含比当前值小的数，如果有，那么就跳过当前循环；如果一个数满足作为开头的条件了，就开始计算序列的长度，用一个变量记录当前的最大序列长度，然后不断更新，最后返回即可。以下是我的代码实现：

这套代码的时间复杂度是O(N)，满足要求。代码也更少，更简洁或者说是更优美，难度也不高，重要的是要有对应的解题思路，下面贴上提交记录截图：

我其实有一个可能比较外行的问题哈，为什么这套代码的时间复杂度是比第一套要低的，但运行时间却更多一些呢，不知道有没有大佬看到我的帖子愿意给我解答一下呢？

4、总结

今天这道题呢，给我的感觉就是，具体的问题要选用针对性的解决方案，由于之前两张帖子写的都是用HashMap，让我思维出现了定式，导致我一开始这道题也要用这个，错过了最佳的选择，这点算是今天吸取到的教训。针对哈希相关的题目应该是告一段落了，接下来应该就是针对双指针的相关题目了，希望能有码友多支持我，我也希望能在csdn遇见更多的同行者，一起进步，后续我找实习、面试以及找到实习后，我也会在帖子中进行一些分享，下次再见啦！