One Cplusplus Solution 12ms


  • 0

    12ms this is my answer. How can I improve it? sad my poor English

    class Solution
    {
    	public:
    	vector<int> twoSum(vector<int>& nums, int target)
    	{
    		struct Node
    		{
    			int index;      //to store the origin index 
    			int num;        //to store the the value of nums
    		};
    
    		//transfer vector<int> nums to vector<int> n_vec  and sort it
    		vector<Node> n_vec;
    		for(int i = 0; i != nums.size(); ++i)
    		{
    			n_vec.push_back(Node{ i, *(nums.begin() + i) });
    		}
    		sort(n_vec.begin(), n_vec.end(), [](Node lh, Node rh) { return lh.num < rh.num; });  
    
    		
    		//to find the index 
    		int i = 0, j = static_cast<int> (nums.size() - 1);
    		while(i < j)
    		{
    			int temp = (n_vec.begin() + i)->num + (n_vec.begin() + j)->num;
    			if(temp<target)
    			{
    				++i;
    			}
    			else if(temp>target)
    			{
    				--j;
    			}
    			else
    			{
    				break;
    			}
    		}
    
    
    		if(i < j)
    		{
    			vector<int> a{ (n_vec.begin() + i)->index, (n_vec.begin() + j)->index };
    			return a;
    		}
    		return vector<int>();
    	}
    };
    

  • 0

    it's inefficient b/c of the while loop takes avg o(n) time.
    The main reason ppl use hashtable is bc it takes o(1) to "find"


  • 1

    I'm sorry. I don't know the meaning of b/c ppl ,but I can almost know what u say.

    Maybe I can use map to rewrite it totally .


Log in to reply
 

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