Longest Consecutive Sequence

Longest Consecutive Sequence

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.

------------- thinking -------------------------------
Bug -> duplication should be considered in this case, this is very important!!!!!!!!!!!!!!!!!!!

https://oj.leetcode.com/discuss/25812/o-n-hashmap-java-solution
https://oj.leetcode.com/discuss/18886/my-really-simple-java-o-n-solution-accepted
https://oj.leetcode.com/discuss/19598/13-line-c-solution
---------------- codes -------------------------------
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int, int> map;
        int longest = 1;
        for(int i = 0; i < num.size(); i++) {
            //bug -> we might have duplications in the array!!!!
            if (map.find(num[i]) != map.end()) {
                continue;
            } else {
                map[num[i]] = 1;
            }
            int pre = num[i] - 1;
            int nxt = num[i] + 1;
            int start = num[i];
            int end = num[i];
            if (map.find(pre) != map.end()) {
                start = num[i] - map[pre];
            }
            if (map.find(nxt) != map.end()) {
                end = num[i] + map[nxt];
            }
            int length = end - start + 1;
            if (length > longest) {
                longest = length;
            }
            map[start] = length;
            map[end] = length;
        }
        return longest;
    }
};