https://leetcode.com/problems/two-sum/

Approach

As we iterate through nums, check if we have a number for target-number in the list. If we do have that number in the list and that number is not the one itself, then we've found two numbers that add up to target.

Solution

1class Solution {
2  public:
3    vector<int> twoSum(vector<int>& nums, int target) {
4      vector<int> ans;
5      unordered_map<int, int> hashtable;
6
7      for(int i=0; i<nums.size(); ++i) {
8        auto it = hashtable.find(target-nums[i]);
9        if(it == hashtable.end()) {
10          hashtable[nums[i]] = i;
11        }
12        else {
13          ans.push_back(i);
14          ans.push_back(it->second);
15          break;
16        }
17      }
18
19      return ans;
20    }
21};

Time Complexity

find() is O(n) worst case but it's O(1) in average. So the total time complexity should be O(N)..

Space Complexity

O(N)