follow up:

如果说给定一个list, 找到含有list中所有元素的最短的区间

[1,2,3,4]

[100, 1, 3, 2, 4, 200, 2, 3, 1] should return [1, 4] because [4, 8] is longer and have the same length

暴力解法就枚举起点和终点

是否可以统计，所有元素的下标集合， 并用max heap保存n个最小的连续元素下标的与目标值的差绝对值，得到目标区间，然后保存最小的区间

{
 100:[0],
 1:[1,8],
 3:[2,7],
 2:[3,7],
 4:[4],
 200:[5]
}

更优的方法是用前向型双指针。

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

Have you met this question in a real interview?

Yes

Clarification

Your algorithm should run in O(n) complexity.

Example

Given[100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is[1, 2, 3, 4]. Return its length:4.

class Solution:
    """
    @param num: A list of integers
    @return: An integer
    """
    #thinking process
    #since the requirement states that we need O(n) time
    #so we can't enumerate the ans based on everyone directly with the list
    #but if we can use O(1) time to know if there is a consecutive subsequence, then 
    #we can do this in O(n) time

    #so if we build a hashmap to indicate the value:index, and scan the list from head
    #for its consecutive part, once include then delete(because it will be included in the ans
    #at most once, keep an winner variable, then the problem should be solved.
    def longestConsecutive(self, num):
        # write your code here
        if not num:
            return 0


        hash = {value:i for i, value in enumerate(num)}
        max_length = 1 #shortest possible
        for item in num:
            if item not in hash:
                continue

            number = item + 1
            cur_count = 1
            #look up
            while number in hash:
                del hash[number]
                number += 1
                cur_count += 1
            number = item - 1 #hang number back to the object of the one hangged by item
            while number in hash:
                del hash[number]
                number -= 1
                cur_count += 1
            max_length = max(max_length, cur_count)
            del hash[item]
        return max_length