LeetCode：Longest Consecutive Sequence

LeetCode：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.

// https://oj.leetcode.com/problems/longest-consecutive-sequence/
// Author : Chao Zeng
// Date   : 2015-3-30
class Solution {
public:
    int longestConsecutive(vector &num) {
        map mp;
        const int NUM = 100;//由於數據中存在負數，所以數組元素加一個偏移量，保證數組下標有效性
        int length = num.size();
        for (int i = 0; i < length; i++){
            mp[num[i] + NUM] = 1;
        }

        int ans;
        int res = 0;
        for (int i = 0; i < length; i++){
            ans = 1;
            if (mp.count(num[i] + NUM)){
                int left = num[i] + NUM - 1;
                while (mp.count(left) && mp[left] != 0){
                    mp[left--] = 0;
                    ans++;
                }

                int right = num[i] + NUM + 1;
                while (mp.count(right) && mp[right] != 0){
                    mp[right++] = 0;
                    ans++;
                }
            }

            if (res < ans){
                res = ans;
            }
        }
        return res;
    }
};