O(n) complexity but not so good in Concrete running time


  • 0
    S

    A hash solution based on the solution of @hossein (discuss). Although it is a implement of O(n) complexity solution, you can see that it can not get result until the position of second element with larger index. That result in more time than some other hash solution. Whatever , this is a neat and clean way.

    class Solution {
    	public:
    		vector<int> twoSum(vector<int> &numbers, int target) {
    			unordered_map<int,int> m;
    
    			for (int i = 0; i < numbers.size(); ++i) 
    				m[numbers[i]] = 0; // value 0 means no such hash key before currently visit
    			for (int i = 0; i < numbers.size(); ++i) 
    			{
    				int ptr=m[target - numbers[i]];
    				if(ptr)
    				{
    					int j;
    					vector<int> result {ptr, i+1};
    					return result;
    				}
    				m[numbers[i]] = i+1;
    			}
    		}
         };
    

Log in to reply
 

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