2016年10月12日星期三

Two Sum III - Data structure design

https://discuss.leetcode.com/topic/32449/trade-off-in-this-problem-should-be-considered



The big data test only have the condition that lots of add and few find. In fact, there has to be one operation's time complexity is O(n) and the other is O(1), no matter add or find. So clearly there's trade off when solve this problem, prefer quick find or quick add.

2个hash(1个nums,一个sums)O(n) add, O(1) find
1个hash O(1) add, less then O(n) find
public class TwoSum {
        Set<Integer> sum;
        Set<Integer> num;
        
        TwoSum(){
            sum = new HashSet<Integer>();
            num = new HashSet<Integer>();
        }
        // Add the number to an internal data structure.
     public void add(int number) {
         if(num.contains(number)){
             sum.add(number * 2);
         }else{
             Iterator<Integer> iter = num.iterator();
             while(iter.hasNext()){
                 sum.add(iter.next() + number);
             }
             num.add(number);
         }
     }
    
        // Find if there exists any pair of numbers which sum is equal to the value.
     public boolean find(int value) {
         return sum.contains(value);
     }
    }
On the other side
public class TwoSum {
    private Map<Integer, Integer> map = new HashMap<Integer, Integer>();

 public void add(int num) {
     map.putIfAbsent(num,0);
     map.put(num,map.get(num)+1);
 }

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

没有评论:

发表评论