Two Sum III – Data structure design LT170

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

Idea 1. Similar to Two Sum LT1, if numbers are unique, set would be enough, otherwise map to store frequency for each number. 遍历hashmap, 对于每个数num，找target – num,

record[num] >= 2 if target – num = num

record[target – num] >= 1 if target – num != num

Time complexity: O(1) for add, O(n) for find, or alternatively add set to store the sum, so that O(n) for add, O(1) for find

Space complexity: O(n)

 public class TwoSum {
     private Map<Integer, Integer> record = new HashMap<>();     public void add(int number) {
         record.put(number, record.getOrDefault(number, 0) + 1);
     }     public boolean find(int value) {
         for(int key: record.keySet()) {
             int another = value - key;
             if(key == another) {
                 if(record.get(another) >= 2) {
                     return true;
                 }
             }
             else {
                 if(record.containsKey(another)){
                     return true;
                 }
             }
         }
         return false;
     }     public static void main(String[] args) {
         TwoSum subject = new TwoSum();
         subject.add(1);
         subject.add(3);
         subject.add(4);
         System.out.println(subject.find(4));
         System.out.println(subject.find(7));
     }
 }

slightly more conciser:

 public class TwoSum {
     private Map<Integer, Integer> record = new HashMap<>();     public void add(int number) {
         record.put(number, record.getOrDefault(number, 0) + 1);
     }     public boolean find(int value) {
         for(int key: record.keySet()) {
             int another = value - key;
             if((key == another && record.get(another) >= 2)
                || (key != another && record.containsKey(another))){
                 return true;
             }
         }
         return false;
     }
 }