My c++ solution ,18ms,STL algorithm used


  • -2
    J
    class Solution2 {
    public:
        vector<int> twoSum(vector<int> &numbers, int target) {
    		vector<int> result;
    		vector<number_index> copy;
    		copy.reserve(numbers.size());
    		int index=0;
    		for(auto it=numbers.begin();it!=numbers.end();it++){
    			copy.push_back(number_index(*it,index++));
    		}
    
    		if(copy.size()<=0){
    			return result;
    		}
            sort(copy.begin(),copy.end(), compare);
    		vector<number_index>::iterator beginSearch = copy.begin();
    		vector<number_index>::iterator endSearch = copy.end();
    		vector<number_index>::iterator tempIt;
    		int lastNum = copy[0]._number+1;
    		number_index tmpTarget;
    
    		while(beginSearch<endSearch){
    			if(beginSearch->_number!=lastNum){
    				tmpTarget._number = target-beginSearch->_number;
    				tempIt = lower_bound(beginSearch+1,endSearch,tmpTarget,compare);
    				if(tempIt!=endSearch){
    					endSearch = tempIt;
    					if(tempIt->_number==tmpTarget._number){
    						result.push_back(tempIt->_index < beginSearch->_index?tempIt->_index:beginSearch->_index);
    						result.push_back(tempIt->_index < beginSearch->_index?beginSearch->_index:tempIt->_index);
    						break;
    					}
    				}
    			}
    			lastNum = beginSearch->_number;
    			beginSearch++;
    		}
    		return result;
        }
    private:
    	struct number_index{
    		int _number;
    		int _index;
    		number_index(int number, int index):_number(number),_index(index){}
    		number_index():_number(0),_index(0){}
    	};
    	static bool compare(const struct number_index& a, const struct number_index& b){
    		return a._number<b._number;
    	}
    };

Log in to reply
 

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