思路
看到"最长"这个关键字，我首先想到的就是动态规划，若能将数组进行排序，即排序完后的数组为[100,200,1,2,3,4]，则求其最大上升序列即可。但由于sort排序的时间复杂度为O(nlogN)，且如何按连续进行排列比较复杂，故舍弃
接着考虑直接双for遍历，则第一层挑选nums[i]作为x，第二层从i+1开始挑选y，若x+1=y，则找到更长连续序列，这样的前提得是有序的数组，否则对于子序列[4,1,3,2]来说，4+1、1+2或3+1均不满足，但实际上，1、2、3、4是符合条件的。故考虑增加判断条件，不仅+1符合，-1也符合，则以4开头向后遍历，找到3时记录值+1，接着以3开始，再次遍历一遍找到2.....，这种查找方式很自然的就能想到使用map或者set结构来做，这样顺其自然的就将查找的动作从O(n)降低到了O(1)
则，整体思路就是外层挑选x，内层通过哈希表以O(1)的时间查找x+1，对于数组来说，x=1可以查找到2、3、4，x为2时可以查找到3、4，显然存在了重复查找，由于是连续序列，则x-1一定不存在序列中，故以此为筛充条件
实现
目录[https://www.jianshu.com/p/85e18c21317a] 题号[https://lee...
3/24 128 最长连续序列 本题基本的算法思想是并查集与哈希表len[i]存储数字i所在的最长连续序列，但其实...
题目链接难度：困难 类型： 哈希 给定一个未排序的整数数组，找出最长连续序列的长度。 要求算法...
最大子序列和 最长连续序列 输入: [100, 4, 200, 1, 3, 2]输出: 4解释: 最长连续序列是 ...
LeetCode-128-最长连续序列 128. 最长连续序列[https://leetcode-cn.com/p...
题目 Given a binary tree, find the length of the longest co...
题目描述：给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。 示例：输入: [1...
https://leetcode-cn.com/explore/interview/card/bytedance/...
题目来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/long...
https://leetcode-cn.com/problems/longest-consecutive-sequ...
本文标题：哈希表--最长连续序列
本文链接：https://www.haomeiwen.com/subject/nekirrtx.html
网友评论