Problem Description
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
Analyze
要求时间复杂度为O(n)，无法使用排序，可以利用hash table。将序列中的所有元素存到一个set（集合）中。对于数组中任意一个元素A[i]，我们可以通过set马上能知道A[i]+1和A[i]-1是否也在序列中。如果在，继续找A[i]+2和A[i]-2，以此类推，最后得到包含A[i]的连续序列，记录此序列的元素个数，最终返回最长连续序列的元素个数。为避免在遍历到A[i+1]时再次重复搜索该序列，在每次搜索的同时我们需要将搜索过的数从set中移除。
Code
class Solution {
func longestConsecutive(nums: [Int]) -> Int {
var set: Set<Int> = Set(nums)
var maxLength = 0
for num in nums {
var length = 0
var num_in = num
while set.contains(num_in) {
set.remove(num_in)
length += 1
num_in += 1
}
num_in = num - 1
while set.contains(num_in) {
set.remove(num_in)
length += 1
num_in -= 1
}
maxLength = max(maxLength, length)
}
return maxLength
}
}
