[recommend for beginners] readable clean C++ implementation


  • -1

    method 1

       class Solution {
        public:
            int longestConsecutive(vector<int>& nums) {
                unordered_map<int, int> map;
                int result=0;
                /*** only update the corner cases ***/
                for(int num : nums){
                    if(map[num]) continue;
                    map[num]=map[num-map[num-1]]=map[num+map[num+1]]=map[num-1]+map[num+1]+1;
                    result=max(result, map[num]);
                }
                return result;
            }
        };
    

    method 2

    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            unordered_set<int> dict(nums.begin(), nums.end());
            int result=1;
            for(int num : nums){
                if(dict.find(num)==dict.end())  continue;
                dict.erase(num);
                /** the (prev, next) is open on both side **/
                int prev=num-1, next=num+1;
                while(dict.find(prev)!=dict.end())  dict.erase(prev--);
                while(dict.find(next)!=dict.end())  dict.erase(next++);
                result=max(result, next-prev-1);
            }
            return result;
        }
    };

  • 1
    2

    I prefer the second solution as the first solution is a little bit tricky and hard to understand. ...........

    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            unordered_set<int> dict(nums.begin(), nums.end());
            int result = 1;
            for(auto num : nums) {
                if(dict.find(num) == dict.end())  continue;
                dict.erase(num);
                int prev = num - 1, next = num + 1;
                while(dict.find(prev) != dict.end())  dict.erase(prev--);
                while(dict.find(next) != dict.end())  dict.erase(next++);
                result = max(result, next - prev - 1);
            }
            return result;
        }
    };

  • 0
    2

    onces AC method 1 solution

    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            unordered_map<int, int> map;
            int result = 0;
            for(auto num : nums) {
                if(map[num])  continue;
                map[num] = map[num-map[num-1]] = map[num+map[num+1]] = map[num-1]+map[num+1]+1;
                result = max(result, map[num]);
            }
            return result;
        }
    };

Log in to reply
 

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