Time Limit Exceeded ! How can i make it better?


  • 0
    B
    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> retV;
            map<int, int> _map;
            for (int i = 0; i < nums.size(); i++) {
                map<int, int>::iterator map_iter = find_if(_map.begin(), _map.end(), EqualJudge(target - nums[i]));
                if (map_iter != _map.end()) {
                    retV.push_back(map_iter->first);
                    retV.push_back(i);
                    return retV;
                }
                else {
                    _map.insert(make_pair(i, nums[i]));
                }
            }
            
            return retV;
        }
        
    private:
        class EqualJudge {
        public:
            EqualJudge(int var) : _var(var) {}
            bool operator() (const pair<int, int> &elem) const {
                return _var == elem.second;
            }
        private:
            int _var;
        };
    };

  • 1
    B

    Do not use find_if, use the find from map interface. find_if will take O(n) time and the map.find O(lgn). Also consider using unordered_map<int, int> for which find takes O(1) amortised time.


Log in to reply
 

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