博文中会简要介绍Leetcode P0128题目分析及解题思路。
“Longest Consecutive Sequence”这道并不算难，但是思路比较巧妙。总体来说有两种思路，一种是通过并查集（Union Find）来不断延长序列长度；另一种则是每次从可能的连续区间最左值开始自增遍历，由此得到连续区间的长度。
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
第一种并查集的思想并不多见，但是也是一个很重要的解题思路。下述Java代码中的第一种解法就借鉴了并查集的思想。对于一个数n而言，n+1、n-1与n本身同属于一个集合，而类似这样的集合，我们若得到其最终的大小，其中最大的就是我们所需要的最长连续区间。
那么如何得到这些集合呢？这里通过维护一个区间的两端来聚合所有可以连接这个区间的值。因为任何一个值n想要连接上某个连续区间，其n-1或n+1势必是这个连续区间的某端，所以核心思路是我们只需要维护一个连续区间两端，将其映射到的其所属的区间的长度，便可以每次都得到连续区间扩展后的长度。
以下是Java的题解代码实现。
class Solution {
public int longestConsecutive(int[] nums) {
Map<Integer, Integer> num2LenMap = new HashMap<>();
int longest = 0;
for (int num: nums) {
if (num2LenMap.containsKey(num))
continue;
// Find the sequence that contains num,
// Here left and right must be some sequence's begin or end
int left = num2LenMap.getOrDefault(num-1, 0);
int right = num2LenMap.getOrDefault(num+1, 0);
// seqLen: length of the sequence in which num exists
int seqLen = left+right+1;
// Keep track of the max length
longest = Math.max(longest, seqLen);
// Keep track of the current length of the sequence in which num is
num2LenMap.put(num, seqLen);
// Extend the length to the boundary(seq) of the sequence
// Do nothing if num has no neighbors
num2LenMap.put(num-left, seqLen);
num2LenMap.put(num+right, seqLen);
}
return longest;
}
}
以下是第二种Java的题解代码。这个代码的主要思路是找到每个连续区间的最小值，然后从最小值开始每次自增然后判断当前值是否在给定的数里存在，若存在则继续自增查找，直到不存在为止，此时就可以得到连续区间的长度。
这里的第二个循环看似是嵌套的两层循环，但实际上每个集合中的元素最多访问一次，所以实际时间复杂度是O(n)的。
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> numSet = new HashSet<>();
for (int num: nums)
numSet.add(num);
int longest = 0;
for (int num: numSet) {
if (numSet.contains(num-1))
continue;
int numInSeq = num;
while (numSet.contains(numInSeq))
++numInSeq;
longest = Math.max(longest, numInSeq-num);
}
return longest;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> num_set;
for (int num: nums)
num_set.insert(num);
int longest = 0;
for (int num: nums) {
if (num_set.count(num-1) > 0)
continue;
int next = num;
while (num_set.count(next) > 0)
++next;
longest = max(longest, next-num);
}
return longest;
}
};