# 0128. Longest Consecutive Sequence
###### tags: `Leetcode` `Medium` `Bloomberg` `FaceBook`
Link: https://leetcode.com/problems/longest-consecutive-sequence/

## 思路 $O(N)$ $O(N)$
如果一点思路都没有，不如从brute force开始想，然后做优化
如果是暴力法的话，拿到一个数x，就开始通过遍历array找以它开始的序列$x+1,x+2,x+3...$
这样的时间复杂度是$O(N^3)$，因为每次找array里面是否存在$x+1,x+2$的过程都要耗费$O(N)$
这时候可以想到用HashSet，只需要$O(1)$，就能找到array里面是否存在这个数
其次，也不用每个数都要找以它开始的序列然后算长度，因为如果$x-1$存在在set里面，之前或之后肯定算过一遍以$x-1$开头的序列，所以只有当$x-1$不在set里面的时候，才需要找以$x$开头的序列算长度

时间复杂度之所以是$O(N)$不是$O(N^2)$是因为while回圈一共执行N次，平均下来，每个for回圈只执行一次while回圈，因此时间复杂度为$O(N)$

**注意：并不是说for里面套while，时间复杂度就一定是$O(N^2)$**

## Code

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int maxLen = 0;
        for(int num:nums) set.add(num);
        for(int num:nums){
            int len=1;
            if(!set.contains(num-1)){
                while(set.contains(num+1)){
                    len++;
                    num++;
                }
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }
}