20210530.md

Algorithm

128. Longest Consecutive Sequence

Description

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

Solution

class Solution {
    public int longestConsecutive(int[] nums) {
        int res = 0;
        // 使用map存储当前元素n的最大序列长度sum
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            if(!map.containsKey(n)){
                // 相邻左侧节点计算左侧的最大长度(没有相邻左侧节点直接设置为0)
                int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
                // 相邻右侧节点计算右侧最大长度
                int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
                // 计算当前左右节点累加之后的长度sum，并保存到n中
                int sum = left + right + 1;
                map.put(n, sum);

                // 求res当前最大值
                res = Math.max(res, sum);

                // 扩大n两侧的数字范围
                // n左侧left个节点，更新为sum
                map.put(n - left, sum);
                // n右侧right个节点，更新为sum
                map.put(n + right, sum);
            }else{
                // 重复元素直接跳过
                continue;
            }
        }
        return res;
    }
}

Discuss

我们也可以采用哈希表来做，刚开始HashMap为空，然后遍历所有数字，如果该数字不在HashMap中，那么我们分别看其左右两个数字是否在HashMap中，如果在，则返回其哈希表中映射值，若不在，则返回0，虽然我们直接从HashMap中取不存在的映射值，也能取到0，但是一旦去取了，就会自动生成一个为0的映射，那么我们这里再for循环的开头判断如果存在映射就跳过的话，就会出错。然后我们将left+right+1作为当前数字的映射，并更新res结果，同时更新num-left和num-right的映射值。

下面来解释一下为啥要判断如何存在映射的时候要跳过，这是因为一旦某个数字创建映射了，说明该数字已经被处理过了，那么其周围的数字很可能也已经建立好了映射了，如果再遇到之前处理过的数字，再取相邻数字的映射值累加的话，会出错。举个例子，比如数组 [1, 2, 0, 1]，当0执行完以后，HashMap中的映射为 {1->2, 2->3, 0->3}，可以看出此时0和2的映射值都已经为3了，那么如果最后一个1还按照原来的方法处理，随后得到结果就是7，明显不合题意。还有就是，之前说的，为了避免访问不存在的映射值时，自动创建映射，我们使用map.containsKey() 先来检测一下，只有存在映射，我们才从中取值，否则就直接赋值为0

Review

Tip

Share