这是一个创建于 2348 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。 题解
这道题目最开始大家想的肯定是 sort，然后计数计算最长序列。但是要求时间复杂度为：o(n)，就不能用 sort 了。一般在 leetcode 中，对时间复杂度有要求，就用空间来换，对空间复杂度有要求，就用时间来换。
基于这种思路我们就想要求最长的，就是要记录下有没有相邻的元素，比如遍历到 100 这个元素，我们需要查看[99, 101]这两个元素在不在序列中，这样去更新最大长度。而记录元素有没有这个事我们太熟悉了，用 set 这种数据结构，而 set 这种数据结构是需要 o(n)的空间来换取的，这就是我们刚才说的用空间来换时间。
class Solution { public int longestConsecutive(int[] nums) { Set<Integer> numsSet = new HashSet<>(); for (Integer num : nums) { numsSet.add(num); } int lOngest= 0; for (Integer num : nums) { if (numsSet.remove(num)) { // 向当前元素的左边搜索,eg: 当前为 100, 搜索：99，98，97,... int currentLOngest= 1; int current = num; while (numsSet.remove(current - 1)) current--; currentLongest += (num - current); // 向当前元素的右边搜索,eg: 当前为 100, 搜索：101，102，103,... current = num; while(numsSet.remove(current + 1)) current++; currentLongest += (current - num); // 搜索完后更新 longest. lOngest= Math.max(longest, currentLongest); } } return longest; } } 热门阅读
 | 1 balaWgc 2019-05-20 08:55:18 +08:00 以后这种文章就别发了行吧 |
 | 2 lovezww2011 2019-05-20 09:17:14 +08:00 你打算每天发一篇吗 |
 | 3 gosansam 2019-05-20 10:04:46 +08:00 我觉得还行呢 |
 | 4 fzy0728 2019-05-20 13:04:07 +08:00 挺棒的 |
 | 5 1069401249 2019-05-20 19:41:58 +08:00 不是 2 层循环吗？时间复杂度不是 0(n)了啊 |
Select Language