Two Sum

array • hash-table
Easy
O(n)O(n)

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Solution

Use a hash map to store value->index while iterating the array.
For each number, check if target - num exists in map; if yes, return the pair of indices.
This is O(n)O(n) time and O(n)O(n) space.

Code Solution

two-sum.cpp
cpp
1
#include <vector>
2
#include <unordered_map>
3
using namespace std;
4


5
vector<int> twoSum(vector<int>& nums, int target) {
6
  unordered_map<int,int> map;
7
  for (int i = 0; i < (int)nums.size(); ++i) {
8
    int need = target - nums[i];
9
    if (map.count(need)) return {map[need], i};
10
    map[nums[i]] = i;
11
  }
12
  return {};
13
}