leetcode128 最长连续序列

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

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

示例:

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

思路：map记录某个连续序列端点的最大长度。

对于数字i，如果已经存在，跳过。

否则：

如果有端点i-1和i+1，合并。

如果只有一边，和本数字合并。

如果相邻数字无端点，自己的长度是1

（你也可以合并的时候移除报废的端点，但是更慢）

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 public int longestConsecutive(int[] nums) {
     
    
   

    

     

    
    

     
 if(nums.length==0)return 0;
     
    
   

    

     

    
    

     

       Map<Integer, Integer> map=new HashMap<>();
     
    
   

    

     

    
    

     
 int ans=1;
     
    
   

    

     

    
    

     
 for(int i:nums){
     
    
   

    

     

    
    

     
 if(!map.containsKey(i)){
     
    
   

    

     

    
    

     
 if(map.containsKey(i-1) && map.containsKey(i+1)){
     
    
   

    

     

    
    

     
 int len=map.get(i-1)+map.get(i+1)+1;
     
    
   

    

     

    
    

     
 if(ans<len)ans=len;
     
    
   

    

     

    
    

     

       map.put(i-1-map.get(i-1)+1,len);
     
    
   

    

     

    
    

     

       map.put(i+1+map.get(i+1)-1,len);
     
    
   

    

     

    
    

     

       map.put(i,-1);
     
    
   

    

     

    
    

     

       }else if(map.containsKey(i-1)){
     
    
   

    

     

    
    

     
 int len=map.get(i-1)+1;
     
    
   

    

     

    
    

     
 if(ans<len)ans=len;
     
    
   

    

     

    
    

     

       map.put(i-1-map.get(i-1)+1,len);
     
    
   

    

     

    
    

     

       map.put(i,len);
     
    
   

    

     

    
    

     

       }else if(map.containsKey(i+1)){
     
    
   

    

     

    
    

     
 int len=map.get(i+1)+1;
     
    
   

    

     

    
    

     
 if(ans<len)ans=len;
     
    
   

    

     

    
    

     

       map.put(i+1+map.get(i+1)-1,len);
     
    
   

    

     

    
    

     

       map.put(i,len);
     
    
   

    

     

    
    

     

       }else{
     
    
   

    

     

    
    

     

       map.put(i,1);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return ans;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

我真的不知道还能怎么优化了。

一些小优化基本没用，我试过了，如果有大变动的做法可以告诉我哈。

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103407905