# 170. (Locked)Two Sum III – Data structure design

Difficulty: Easy

Frequency: N/A

Design and implement a TwoSum class. It should support the following operations: add and find.

add(input) – Add the number input to an internal data structure.
find(value) – Find if there exists any pair of numbers which sum is equal to the value.

For example,

Solution 1:
Data structure:
unordered_map
Complexity:
Time:
find: O(n) worst case  —->not O(1) ? average
Space: O(n)
Code:
```
class two_sum {
unordered_map&lt;int, int&gt; num_count_map;

void add(int new_num) {
if (num_count_map[new_num]) {
num_count_map[new_num] = num_count_map[new_num] + 1;
} else {
num_count_map[new_num] = 1;
}
}

bool find(int target) {
unordered_map&lt;int, int&gt;::iterator map_iter;
for (map_iter = num_count_map.begin(); map_iter != num_count_map.end(); map_iter++) {
int num_to_find = target - map_iter-&gt;first;
if (num_count_map.find(num_to_find)) {
if (num_to_find != map_iter-&gt;first) {
return true;
} else {
if (map_iter-&gt;second &gt; 1) {
return true;
}
}
} else {
return false;
}
}
}
}
```

Things to learn:

## One thought on “170. (Locked)Two Sum III – Data structure design”

1. […]  Two Sum III – Data structure design […]

Like