leetcode 128. Longest Consecutive Sequence | 128. 最长连续序列（Java）

谁践踏了优雅 2023-01-23 14:54 134阅读 0赞

## 题目 ##

[https://leetcode.com/problems/longest-consecutive-sequence/][https_leetcode.com_problems_longest-consecutive-sequence]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

#### 方法1：HashMap 解法，O(n^2) ####

如下图，假设 n=4 被插入，count 的变化如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public int longestConsecutive(int[] nums) { 
            HashMap<Integer, Integer> dp = new HashMap<>();
            for (int n : nums) { 
                if (!dp.containsKey(n)) { 
                    int count = 1; // 以n结尾的最长连续序列长度
                    if (dp.containsKey(n - 1)) { 
                        count += dp.get(n - 1); // dp(n)=dp(n-1)+1
                    }
                    dp.put(n, count);
                    // 比n大的连续key，将value依次累加dp(n)
                    int next = n + 1;
                    while (dp.containsKey(next)) { 
                        dp.put(next, dp.get(next) + count);
                        next++;
                    }
                } // else, duplicate, do nothing
            }
            int max = 0;
            for (int k : dp.keySet()) { 
                max = Math.max(max, dp.get(k));
            }
            return max;
        }
    }

#### 方法2：官方题解，O(n) ####

[https://leetcode.com/problems/longest-consecutive-sequence/solution/][https_leetcode.com_problems_longest-consecutive-sequence_solution]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

class Solution { 
        public int longestConsecutive(int[] nums) { 
            Set<Integer> num_set = new HashSet<Integer>();
            for (int num : nums) { 
                num_set.add(num);
            }
    
            int longestStreak = 0;
    
            for (int num : num_set) { 
                if (!num_set.contains(num-1)) { 
                    int currentNum = num;
                    int currentStreak = 1;
    
                    while (num_set.contains(currentNum+1)) { 
                        currentNum += 1;
                        currentStreak += 1;
                    }
    
                    longestStreak = Math.max(longestStreak, currentStreak);
                }
            }
    
            return longestStreak;
        }
    }

#### 方法3：dp ####

1.  如果 num 的加入使连续序列的长度增加，那么一定是因为它与 num-1 或 num+1 连成了一片。
2.  连成一片后，只需要让连续序列的两个端点保持最新记录，不需要关心除端点以外的元素。

class Solution:
        def longestConsecutive(self, nums: List[int]) -> int:
            result = 0
    
            record = { }
            for num in nums:
                if num in record: continue
    
                l, r = num, num
                if num - 1 in record:
                    l = record[num - 1][0]
                if num + 1 in record:
                    r = record[num + 1][1]
    
                if r - l + 1 > result:
                    result = r - l + 1
    
                record[num] = (l, r) # 占位，避免重复
                record[l] = (l, r)
                record[r] = (l, r)
            for r in record:
                print(str(r) + ": " + str(record[r]))
            return result

[https_leetcode.com_problems_longest-consecutive-sequence]: https://leetcode.com/problems/longest-consecutive-sequence/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221004/479a6c8f81ff4c67975bd059f7dab352.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221004/a4eb3433c9284795aa695c94258ae285.png
[https_leetcode.com_problems_longest-consecutive-sequence_solution]: https://leetcode.com/problems/longest-consecutive-sequence/solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221004/7d6111a5bdf2491bb3ecf7752ae5420e.png