Hashtable solution to 2 sum

Question

public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int size = nums.size();
        vector<int> toRet;
        unordered_map<int,pair<int,int>> myMap;
        for(int i = 0; i < size; ++i){
            myMap.emplace(nums[i],make_pair(nums[i],i));
        }
        for(int i = 0; i < size; ++i){
            int toFind = target - nums[i];
            if(myMap[toFind].first == toFind && myMap[toFind].second != i){
                toRet.push_back(i);
                toRet.push_back(myMap[toFind].second);
                return toRet;
            }
        }
        return toRet;
    }
};

How do I make this run faster? I can't think of anything. Right now, it is slower than 47% of submissions. Could you please provide some hints?

Answer 1

It's possible to solve this in a single pass:

• Use a map<int, int> to store values you've seen so far, and their first index, let's call it seen
• For each value, let's call it current:
  • Is target - current in seen?
    • If yes, return the pair of the index in the map and the current index
    • If not, and current is not yet in seen, then put current into seen and the current index
• If you reached the end of the collection without returning, then there is no such pair that sum to target.

This algorithm should be faster than the posted code, because:

• it works in a single pass
• uses less memory (unordered_map<int,pair<int,int>> replaced with unordered_map<int, int>)
• uses fewer conditions