Another 12ms C++ solution


  • 0
    G

    step1: copy the vector.

    step2: sort the copy of vector using stl sort.

    step3; binary search the sorted vector.

    step4: find the index of the 2 numbers. also use the stl find.

    step5. create the return vector.

    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
    		vector<int> tempnums=nums;
    		sort(tempnums.begin(), tempnums.end());
    		int num1,num2;
    		vector<int>::iterator itl, itr, itm, it, ite=tempnums.end(), itb=tempnums.begin();
    		
    		bool found=false;
    		for (it=itb; it!= ite; ++it)
    		{
    			num1=*it;
    			num2=target-num1;
    			itl=it+1;
    			itr=ite;
    			while(itl != itr)
    			{
    				itm=itl+(itr-itl)/2;
    				if(*itm == num2) 
    				{
    					found=true;
    					break;
    				}
    				else if (*itm < num2)
    				{
    					itl=itm+1;
    					continue;
    				}
    				else 
    				{
    					itr=itm;
    					continue;
    				}
    			}
    			if (found)
    			{
    				break;
    			}
    		}
    		vector<int>::size_type index1, index2;
    		vector<int>::iterator it1, it2;
    		itb=nums.begin();
    		ite=nums.end();
    		it1=find(itb, ite, num1);
    		if (num1==num2)
    		{
    			it2=find(it1+1, ite, num2);
    		}
    		else
    		{
    			it2=find(itb, ite, num2);
    		}
    		index1=it1-itb+1;
    		index2=it2-itb+1;
    		vector<int> result;
    		result.push_back(min(index1, index2));
    		result.push_back(max(index1, index2));
    		return result;
        }
    };

Log in to reply
 

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