leetcode.哈希表.128最长连续序列-Java

1. 具体题目

给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。

示例:

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

2. 思路分析

由于题目中不要求连续序列中的元素在原数组中是有序的，对于一个数只要查找数组中是否有与其相邻的数即可，所以考虑将元素存入HashSet中，实现 O(1)时间的查询。

3. 代码

 public int longestConsecutive(int[] nums) {

         HashSet set = new HashSet();

         int longest = 0;

         for(int num : nums){

             set.add(num);

         }

         for(int num : nums){

                 if(set.remove(num)){

                 int count = 1;

                 int current = num;

                 while(set.remove(--current)) count++;

                 current = num;

                 while(set.remove(++current)) count++;

                 longest = Math.max(longest, count);

              }

         }

         return longest;

 }

巴特西

leetcode.哈希表.128最长连续序列-Java

最新文章

热门文章