本文共 1725 字，大约阅读时间需要 5 分钟。

public int longestConsecutive(int[] num) {        int res = 0;        HashSet
   
     set = new HashSet
    
     ();        for(int i = 0; i < num.length; i++)            set.add(num[i]);        for(int i = 0; i < num.length; i++){            if(set.contains(num[i])){                int head = num[i], tail = num[i];                int cur_len = 1;                set.remove(head);                while(set.contains(head - 1) || set.contains(tail + 1)){                    if(set.contains(head - 1)){                        head--;                        set.remove(head);                        cur_len++;                    }                    if(set.contains(tail + 1)){                        ++tail;                        set.remove(tail);                        cur_len++;                    }                }                res = Math.max(res, cur_len);            }        }        return res;    }
    
   

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,

Your algorithm should run in O(n) complexity.

public int longestConsecutive(int[] num)

之前这一题tag里面是有一条HashSet的，但后来没了，估计是作者觉得给了这个提示答案就太明显了。

那我们就跟据这个提示走，实际上知道要用HashSet之后，就不难了。可以认为这是一个HashSet比较特殊的用法，我想这属于一种利用HashSet进行伪排序。中心思想是这样的：假如这个input不是数组，是HashSet，该怎么做？ 那么我们在遍历这个HashSet的时候，当我们遍历到100，那么我们就尝试同时往左右两边试探，看看99和101在不在。当然，在示例里都不存在，所以我们往下走，走到4，继续左右试探，然后发现3在，再试探，发现2和1都在。于是乎我们有了一个长度为4的临时答案。别忘了，当我们每扫到一个元素（包括正常遍历和左右试探）我们都要在HashSet里面删掉它以免重复遍历的情况出现。继续回到刚才的解题过程，当我们最后扫到200的时候，发现其左右也不存在，到这个时候扫描已经完毕了。所以这一题的答案就是我们刚才扫到的最大的值4.

下面就给出代码吧：

转载地址：http://ogaxb.baihongyu.com/