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