leetcode128 最长连续序列

分手后的思念是犯贱 2023-06-19 09:46 78阅读 0赞

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

要求算法的时间复杂度为 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;
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191205164404249.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70