2015年10月24日星期六

Leetcode 170 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

Solution 1: Use hash table, add is O(1) and find is O(n), not sure why now it TLE.
 public class TwoSum {  
   Map<Integer,Integer> map=new HashMap<>();  
   // Add the number to an internal data structure.  
      public void add(int number) {  
        if (!map.containsKey(number)) map.put(number,1);  
        else map.put(number,map.get(number)+1);  
      }  
   // Find if there exists any pair of numbers which sum is equal to the value.  
      public boolean find(int value) {  
     for (Map.Entry<Integer, Integer> entry : map.entrySet()) {  
       int i = entry.getKey();  
       int j = value - i;  
       if ((i == j && entry.getValue() > 1) || (i != j && map.containsKey(j))) {  
         return true;  
       }  
     }  
     return false;  
      }  
 }  

没有评论:

发表评论