My c++ solution with one pass


  • 0
    S
    class Solution {
        public:
            int longestConsecutive(vector<int> &num) {
                int res = 0;
                unordered_map<int, int> h;
                for (auto& x: num) {
                    if (!h[x]) {
                        h[x] = 1 + h[x+1] + h[x-1];
                        if (h[x+1]) h[h[x+1]+x] = h[x]; 
                        if (h[x-1]) h[x-h[x-1]] = h[x];
                    }
                    res = max(h[x], res);
                }
    
                return res;
            }
    };
    

    The idea is to build a map on the way. The key is the number, the value means the length of the sequence which has the key as one of its borders.

    we iterate each value in the num array, if it resides in the map, just ignore. Else, we find the two adjcent sequences from left and right, and combine them into one seq. after that, we update the value of the borders of the new seq to the length of the seq.


Log in to reply
 

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