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,
add(1); add(3); add(5); find(4)true; find(7)false


Solution 1:
Data structure:
unordered_map
Complexity:
Time:
add: O(1)
find: O(n) worst case  —->not O(1) ? average
Space: O(n)
Code:

class two_sum {
         unordered_map<int, int> 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<int, int>::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->first;
                             if (num_count_map.find(num_to_find)) {
                                       if (num_to_find != map_iter->first) {
                                                 return true;
                                       } else {
                                                 if (map_iter->second > 1) {
                                                          return true;
                                                 }
                                       }
                             } else {
                                       return false;
                             }
                    }
          }
}

Things to learn:
Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s