[LeetCode] Two Sum

This is a classic problem for hash table. The basic idea is to maintain a hash table for each element in nums, using the element as key and its index (in this problem, 1-based) as value. Then for each num of nums, search for target - num in the hash table. If it is found and is not the same as num, then we are done. Notice that the problem statement has excluded the case of duplicates by stating that "each input would have exactly one solution".

Now you may quickly write down the following code.

 1 vector<int> twoSum(vector<int>& nums, int target) {
 2     vector<int> ans;
 3     unordered_map<int, int> mp;
 4     for (int i = 0; i < nums.size(); i++)
 5         mp[nums[i]] = i + 1;
 6     for (int i = 0; i < nums.size(); i++) {
 7         if (mp.find(target - nums[i]) != mp.end() && mp[target - nums[i]] != i + 1) {
 8             ans.push_back(i + 1);
 9             ans.push_back(mp[target - nums[i]]);
10             return ans;
11         }
12     }
13 }

Notice the above code has two for loops to iterate over nums. In fact, the process of building the hash table and searching in it can be done in one pass. Each time before you add a num to mp, just search for target - num first. The code now becomes as follows.

 1 vector<int> twoSum(vector<int>& nums, int target) {
 2     vector<int> ans;
 3     unordered_map<int, int> mp;
 4     for (int i = 0; i < nums.size(); i++) {
 5         if (mp.find(target - nums[i]) != mp.end() && mp[target - nums[i]] != i + 1) {
 6             ans.push_back(mp[target - nums[i]]);
 7             ans.push_back(i + 1);
 8             return ans;
 9         }
10         mp[nums[i]] = i + 1; 
11     }
12 }