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;
}