27ms c++ solution


  • -1
    Y
    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            if(nums.size() == 0) return 0;
            int max = 0;
            unordered_map<int, pair<int, int> > mark;
            for(int i = 0; i < nums.size(); i ++) {
                int n = nums[i];
                int head = n, tail = n;
                unordered_map<int, pair<int, int> >::iterator it;
                it = mark.find(n);
                if(it != mark.end()) continue;
                it = mark.find(n - 1);
                if(it != mark.end()) {
                    head = it->second.first;
                }
                it = mark.find(n + 1);
                if(it != mark.end()) {
                    tail = it->second.second;
                }
                
                pair<int, int> p(head, tail);
                mark[n] = p;
                mark[head].second = tail;
                mark[tail].first = head;
                int cur = tail - head + 1;
                if(cur > max) max = cur;
            }
            
            return max;
        }
    };
    

    ps: use unordered_map is much faster than map.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.