The “Two Sum Problem” is described as follows:

*Given an array of integers nums and an integer target, return the indices of the two integers in nums such that they add up to target.* See Leetcode “Two Sum Problem”

A solution with a time complexity of \(O(n)\) in pseudocode solution looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

array nums // contains random number of elements
target
array result_indices
set partial_sums
map indices_map
for i in len(nums):
n = nums[i]
if target - n is in partial_sums:
result_indices.add(i)
result_indices.add(indices_map[target - n])
partial_sums.add(n)
indices_map[n] = i

Iterate once over all elements in `nums`

.

- Check if the partial sum
`target - n`

is in`partial_sums`

. If this is the case a matching pair whose sum results in`target`

was found, because`n + targer - n = target`

. If`target - n`

is in`partial_sums`

its index is also in`indices_map`

therefore the index pair can be added to`result_indices`

. - Add
`n`

to`partial_sums`

(such that it can be found in a subsequent iteration). - Add the index
`i`

of`n`

to`indices_map`

(such that it can be found in a subsequent iteration).

The output of this solution is the array `result_indices`

which contains index pairs that result in `target`

. If `result_indices`

is empty no solution was found. It is obvious why this solution runs in \(O(n)\) because each element of `nums`

is only accessed once and the containers `partial_sum`

and `indices_map`

have insert and access complexities of \(O(1)\).

A possible solution in C++ (17) looks like this:

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
31
32

#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// find indices
vector<int> result_indices;
unordered_set<int> partial_sums;
unordered_map<int, int> indices_map;
// iterate once over all elements in nums
for (size_t i = 0; i < nums.size(); i++) {
int n = nums.at(i);
// check if the target minus the current element is in the set sums
// if that is the case a solution has been found because:
// n + (target - n) == target
const bool is_in = partial_sums.find(target - n) != partial_sums.end();
if (is_in) {
result_indices.push_back(i);
result_indices.push_back(indices_map.at(target - n));
}
partial_sums.insert(n);
indices_map.insert({n, i});
}
return result_indices;
}
};