今天和大家聊的问题叫做 最长连续序列，我们先来看题面：https://leetcode-cn.com/problems/longest-consecutive-sequence/
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
Follow up: Could you implement the O(n) solution?
题意
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？
样例
示例 1： 输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 示例 2： 输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9
解题
这道题, 难在时间复杂度限定在O(n), 要不排序就可以了!
思路一:集合
集合,查询时间复杂度为O(1)
class Solution { public int longestConsecutive(int[] nums) { Set<Integer> num_set = new HashSet<>(); for (int n : nums) num_set.add(n); int res = 0; for (int num : num_set) { if (!num_set.contains(num - 1)) { int tmp = 1; while (num_set.contains(num + 1)) { tmp++; num++; } res = Math.max(res, tmp); } } return res; } }
思路二:字典
遍历数组, 用字典(哈希)记录目前与该值可以组成最长连续序列.
class Solution { public int longestConsecutive(int[] nums) { HashMap<Integer, Integer> lookup = new HashMap<>(); int res = 0; for (int num : nums) { if (!lookup.containsKey(num)) { // 查看左右两边是否可以相连 int left = (lookup.containsKey(num - 1)) ? lookup.get(num - 1) : 0; int right = (lookup.containsKey(num + 1)) ? lookup.get(num + 1) : 0; lookup.put(num, left + right + 1); // 改变首尾两个长度(换成更长的长度) lookup.put(num - left, left + right + 1); lookup.put(num + right, left + right + 1); res = Math.max(res, left + right + 1); } } return res; } }
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
