128. 最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

本题初看上去没有任何思路，但是这道题的简单描述，以及时间复杂度的限制等等条件都已经告诉我们这道题该怎么做了。
因为暴力法需要排序，那很显然如果要有这么低的复杂度，就必须要空间换时间。
那顺着这个角度去思考，空间里需要放什么呢？
暴力法我们是可以先排序，也可以直接枚举每个数，看他之前或者之后有没有数，那我们可以用一个set把所有数都找出来，遍历到100的时候查找101，或者99有没有，这都是复杂度为O(1)的操作，那枚举n次 看似复杂度是O(n)其实不然，因为每次操作都稍显复杂了，我们其实只需往大或者往小判断是否存在这个数即可，因为当我们判断一个数的大或者小存在时，是重复操作了。
例如本题，当遍历到4，我们会形成1,2,3,4的序列，当遍历到1,又会有1,2,3,4的序列。因此我们只要判断一个数的大或者小是否存在即可。
然后再均摊一下，复杂度成功到了O(n)
代码如下:

class Solution {
    public int longestConsecutive(int[] nums) {
        
        Set <Integer> set = new HashSet<>();
        for (int n : nums){
            set.add(n);
        }
        int longestLen = 0;
        for (int i = 0 ;i < nums.length ; i++){
            
            int x = nums[i];
            int currentLen = 1;
            while (set.contains(x-1)){
                x = x - 1;
                currentLen++;
            }

            if (currentLen > longestLen)
                longestLen = currentLen;
        }
        return longestLen;
        
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-consecutive-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。