# Two Sum Problem

## Description

LeetCode Problem 1. Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Example:

``````1
2
3
Input: nums = [2,7,11,15], target = 9.
Output: [0,1].
Explanation: As nums[0] + nums[1] = 2 + 7 = 9, we return [0, 1].
``````

## Solution

#### Brute Force Approach

A simple solution is to use the `brute force` approach.

We loop through each element x in the array. For each element, we loop through the rest elements again to see whether target-x exists.

The time complexity of this approach is O(n2), and the space complexity is O(1).

#### Hash Table Approach

We can use `hash table` to reduce the time complexity.

For each element x in the array, we use a hash table to store the <x, index> pair, indicating we have encountered a value x and its index in the array.

When we loop through the array, we would like to know whether the sum a newly encountered element x’ and a previously encoutered element x is target (x + x’ = target). We can search (target-x’) in the hash table to see if we have encountered such an x before.

If such an x exists, we are done; otherwise, we can keep on looping through the array.

With the help of the hash table, we only need to loop through the array once. Thus, the time complexity can be reduced to O(n), while the space complexity will be increased to O(n).

## Sample C++ Code

This is a C++ implementation of the hash table approach.

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> ht;
vector<int> ans;
for (int i = 0; i < nums.size(); i ++) {
int xprime = nums[i];
int x = target - xprime;
if (ht.find(x) != ht.end()) {
ans.push_back(ht[x]);
ans.push_back(i);
break;
}
ht[xprime] = i;
}
return ans;
}

int main() {
vector<int> nums={2, 7, 11, 15};
int target = 9;
vector<int> ans;
ans = twoSum(nums, target);
cout << ans[0] << " " << ans[1] << endl;
}
``````