[LeetCode] Two Sum

The basic idea is to maintain a hash table for each element num in nums, using num as key and its index (1-based) as value. For each num, search for target - num in the hash table. If it is found and is not the same element as num, then we are done.

The code is as follows. Note that each time before we add num to mp, we search for target - num first and so we will not hit the same element.

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