The best data structure I could come up with is the map (hashing based approach)
insert(num)
: O(1) for unordered/hash map
find(sum)
: O(N)
What I will do is that when I would get an insert query, I'll just increase the count of the num stored in my map by 1. And when I'll get the find query, I'll just iterate over the keys of the map and will try to find out if sum - key entry is present in the map or not, if present and key != sum/2 then directly return the pair or else if key == sum/2 and count of key > 1 then return the pair otherwise continue with my search over the keys.
And the c++ code would look like this:
void insert(int num) {
my_map[num]++;
}
pair<int, int> find(int sum) {
for (auto it = my_map.begin(); it != my_map.end(); it++) {
int key = it->first;
int res = sum - key;
if (my_map.find(res) != my_map.end()) {
if (2 * key == sum) {
if (my_map[key] > 1) {
return {key, key};
} else {
return {INT_MIN, INT_MIN};
}
} else if (my_map[res] > 0) {
return {key, res};
} else {
return {INT_MIN, INT_MIN};
}
}
}
return {INT_MIN, INT_MIN};
}