How can I do it faster (20ms)


  • 0
    S

    I iterate over the array, and I use the hash table to find ( target -nums[i])
    If there is any, then is done.
    hash table provide average O(1) complexity so I think this is quite fast.
    Is there other faster way? I saw some posts using map to solve this, why is it faster?

    class Solution{
    public:
    	typedef struct pair {
    	public:
    		int index;
    		int content;
    	}myPair;
    
    	vector<int> twoSum(vector<int>& nums, int target) {
    		vector<int> res;
    		hash myHash(nums);
    		myPair* resPair=NULL;
    		int i = 0;
    		for (i = 0; i <nums.size(); i++) {
    			resPair = myHash.findPair(target - nums[i]);
    			if (resPair == NULL)
    				continue;
    			else if (resPair->index == i)
    				continue;
    			else
    				break;
    			
    		}
    
    		if (resPair == NULL || resPair->index == i)
    		{
    			res.push_back(3); res.push_back(4);
    		}
    
    		res.push_back(i + 1);
    		res.push_back((resPair->index) + 1);
    		sort(res.begin(), res.end());
    
    		return res;
    	}
    
    	class hash {
    	public:
    		hash(vector<int>& nums) {
    			bucketSize = nums.size();
    			hashTable.reserve(bucketSize);
    			for (int i = 0; i < nums.size(); i++) {
    				vector<myPair> tmp;
    				hashTable.push_back(tmp);
    			}
    				
    			for (int i = 0; i <nums.size(); i++)
    			{
    				insertTarget(nums[i], i);
    			}
    		}
    
    		~hash() {}
    
    		myPair* findPair(int num) {
    			
    			int k = getKey(num);
    
    			return linearSearch(k, num);
    
    		}
    
    		myPair* linearSearch(int k, int num) {
    
    			for (int i = 0; i <hashTable[k].size(); i++)
    				if (hashTable[k][i].content == num)
    				return &hashTable[k][i];
    			return NULL;
    		}
    
    		int getKey(int target) {
    			if (target < 0)
    				target = 0 - target;
    			return (target) % bucketSize;
    			
    		}
    
    		void insertTarget(int number, int index) {
    			int k = getKey(number);
    			myPair newPair;
    			newPair.content = number;
    			newPair.index = index;
    			hashTable[k].push_back(newPair);
    		}
    
    	private:
    		vector<vector<myPair>> hashTable;
    		int bucketSize;
    	};
    };

Log in to reply
 

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