Two Sum III - Data structure design

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

add - Add the number to an internal data structure.

find - 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

Analysis

Store all numbers into a hash table. The key is the number, and the value is how many times the number has occurred. The reason to use a hash table instead of a hash set is to deal with the case like: 4=2+2.

Complexity

Time: O(1) for add, O(n) for find

Space: O(n)

Code

Java

public class TwoSum {
  Map<Integer, Integer> counters = new HashMap<>();

  public void add(int number) {
    int count = 1;
    if (counters.containsKey(number)) {
      count = counters.get(number) + 1;
    }
    counters.put(number, count);
  }

  public boolean find(int value) {
    for (int num : counters.keySet()) {
      int target = value - num;
      if (counters.containsKey(target) && (target != num || counters.get(num) > 1)) {
        return true;
      }
    }
    return false;
  }
}