0128. 最长连续序列 · ttttt

# 0128. 最长连续序列 ## 题目地址(128. 最长连续序列) <https://leetcode-cn.com/problems/longest-consecutive-sequence/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。 ``` ``` ## 前置知识 - hashmap ## 公司 - 阿里 - 腾讯 - 百度 - 字节 ## 思路这是一道最最长连续数字序列长度的题目，官网给出的难度是`hard`. 符合直觉的做法是先排序，然后用一个变量记录最大值，遍历去更新最大值即可，代码： ``` <pre class="calibre18">``` if (nums.length === 0) return 0; let count = 1; let maxCount = 1; // 这里其实可以不需要排序，这么做只不过是为了方便理解 nums = [...new Set(nums)].sort((a, b) => a - b); for (let i = 0; i < nums.length - 1; i++) { if (nums[i + 1] - nums[i] === 1) { count++; } else { if (count > maxCount) { maxCount = count; } count = 1; } } return Math.max(count, maxCount); ``` ``` 但是需要排序时间复杂度会上升，题目要求时间复杂度为 O(n), 那么我们其实可以不用排序去解决的。思路就是将之前”排序之后，通过比较前后元素是否相差 1 来判断是否连续“的思路改为不排序而是`直接遍历，然后在内部循环里面查找是否存在当前值的邻居元素`，但是马上有一个问题，内部我们`查找是否存在当前值的邻居元素`的过程如果使用数组，时间复杂度是 O(n), 那么总体的复杂度就是 O(n^2)，完全不可以接受。怎么办呢？我们换个思路，用空间来换时间。比如用类似于 hashmap 这样的数据结构优化查询部分，将时间复杂度降低到 O(1), 代码见后面`代码部分` ## 关键点解析 - 空间换时间 ## 代码 ``` <pre class="calibre18">``` /** * @param {number[]} nums * @return {number} */ var longestConsecutive = function(nums) { set = new Set(nums); let max = 0; let temp = 0; set.forEach(x => { // 说明x是连续序列的开头元素 if (!set.has(x - 1)) { temp = x + 1; while (set.has(y)) { temp = temp + 1; } max = Math.max(max, y - x); // y - x 就是从x开始到最后有多少连续的数字 } }); return max; }; ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(N)O(N)O(N) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经 37K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)