C++ solution, 8ms, beats 98.35%


  • 0

    Actually, this is another way to implement the third editorial solution, Approach #3 (One-pass Hash Table).
    Instead of unordered_map, it uses an array as hash table.
    So, it may require a large amount of memory if the range of nums is too wide.

    class Solution {
    public:
    	vector<int> twoSum(vector<int>& nums, int target)
    	{
    		auto len = nums.size();
    
    		if (len < 2)
    			return {};
    
    		int min = nums[0], max = min;
    
    		for (auto n : nums)
    		{
    			if (n < min)
    				min = n;
    			else if (n > max)
    				max = n;
    		}
    
    		int mmin = (target - max > min) ? target - max : min;
    		int mmax = (target - min < max) ? target - min : max;
    		int nmap[mmax - mmin + 1];
    		
    		memset(nmap, 0, sizeof(nmap));
    
    		for (auto i = 0; i < len; ++i)
    		{
    			auto n = nums[i];
    
    			if (n < mmin || n > mmax)
    				continue;
    
    			auto j = nmap[target - n - mmin];
    			if (j == 0)
    				nmap[n - mmin] = i + 1;
    			else
    				return {j-1, i};
    		}
    
    		return {};
    	}
    };
    

Log in to reply
 

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