A simple C++,solution using unordered_set.And simple consideration about this problem
I have seen a lot of discussion about this problem.In my opinion,it is not correct to use set(which is ordered),because very time we insert an element to a orde
I have seen a lot of discussion about this problem.In my opinion,it is not correct to use set(which is ordered),because very time we insert an element to a ordered set,it will cost O(n),so the total complexity is O(nlogn),which violates the request of the problem.So here we use an unordered_set,and one is enough.\n\nBesides,to think about this problem,one principle issue we should realize is that usually when we want to reduce the time complexity,we have to increase the space complexity.In this case,if we want to access an element within O(1),we have to use hash table.\n\n    class Solution {\n    public:\n        int longestConsecutive(vector<int> &num) {\n            unordered_set<int> record(num.begin(),num.end());\n            int res = 1;\n            for(int n : num){\n                if(record.find(n)==record.end()) continue;\n                record.erase(n);\n                int prev = n-1,next = n+1;\n                while(record.find(prev)!=record.end()) record.erase(prev--);\n                while(record.find(next)!=record.end()) record.erase(next++);\n                res = max(res,next-prev-1);\n            }\n            return res;\n        }\n    };
[]