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

Naive Way: Use a HashTable to store added numbers. If I want to make add operation O(1), then find operation requires O(n) to go through the HashTable. If I want to make find operation O(1), then the add operation requires O(n) to generate all possible two sums.

add O(1), find O(n), space O(n^2)

 // add O(n), find O(1), space O(n^2)  
      Set<Integer> twoSums = new HashSet<Integer>();  
      Set<Integer> ints = new HashSet<Integer>();  
       public void add(int n){  
            Iterator<Integer> iter = ints.iterator();  
            while(iter.hasNext()){  
                 twoSums.add(iter.next()+n);  
            }  
            ints.add(n);  
       }  
       public boolean find(int n){  
            return twoSums.contains(n);  
       }  

add O(n), find O(1), space O(n)

 // add O(1), find O(n), space O(n)  
      Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
      public void add(int n){  
           if(map.containsKey(n))  
                map.put(n,map.get(n)+1);  
           else  
                map.put(n,1);  
      }  
      public boolean find(int n){  
           Iterator iter = map.entrySet().iterator();  
           while(iter.hasNext()){  
                Entry cur = (Entry)iter.next();  
                if(map.containsKey(n-(int)cur.getKey())){  
                     if(n == 2*(int)cur.getKey())  
                          return (int)cur.getValue()>=2;  
                     else  
                          return true;  
                }  
           }  
           return false;  
      }