8、Longest Consecutive Sequence（Hard）

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
    }
}