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.

Example 1:

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Example 2:

add(3); add(1); add(2);
find(3) -> true
find(6) -> false

第一种方法， 用hash map建立映射，要注意的是，当找到diff 和num相等时，一定要判断一下num在map中的数量，因为当他们相等时，num在map中的数量必须大于0；add 时间复杂度O(1)，find 时间复杂度O(N),空间复杂度o(N)

class TwoSum {
    
    HashMap<Integer,Integer> map = null;
    /** Initialize your data structure here. */
    public TwoSum() {
        map = new HashMap<>();
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        map.put(number,map.getOrDefault(number,0) + 1);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        int diff = 0;
        
        for(int num : map.keySet()){
            diff = value - num;
            
            if(map.containsKey(diff)){
                if(diff !=num || map.get(diff) > 1 ){
                    return true;
                }
            }
        }
        
        return false;
    }
}

two pointer 算法可以将find 时间复杂度优化到 o(nlogn) //nlogn 比o(n) 慢 Java的collection sort的时间复杂度是 o(nlogn)

class TwoSum {   
    List<Integer> list = null;
    public TwoSum() {
        list = new ArrayList<>();
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        list.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        
        Collections.sort(list);
        
        for(int i = 0, j = list.size()-1; i < j ; ){
            int sum = list.get(i) + list.get(j);
            if( sum == value){
                return true;
            }
            else if(sum < value){
                i++;
            }else{
                j--;
            }
        }
        
        return false;
    }
}

map+list 循环list比循环map要快

存o(1),取o(n)

class TwoSum {
    
    private List<Integer> list;
    private Map<Integer,Integer> map;
    /** Initialize your data structure here. */
    public TwoSum() {
        this.list = new ArrayList<>();    
        this.map = new HashMap<>();
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if(map.containsKey(number))
            map.put(number,map.get(number)+1);
        
        else{
            map.put(number,1);
            list.add(number);
        }
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        
        
        for(int num : list){
            int num2 = value - num;
            
            if(num == num2 && map.get(num) > 1 || num != num2 && map.containsKey(num2)) return true;
            
        }
        
        return false;
    }
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * boolean param_2 = obj.find(value);
 */

这个方法 超时了，理论上 存 o(n),取 o(1)

class TwoSum {
    
    
    // private Map<Integer,Integer> map = null;
    private Set<Integer> set = null;
    private List<Integer> list = null;
    /** Initialize your data structure here. */
    public TwoSum() {
        // map = new HashMap<>();
        set = new HashSet<>();
        list = new ArrayList<>();
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if(list.size() == 0) list.add(number);
        
        else{
            for(int i : list){
                set.add(number+i);
            }
            list.add(number);
        }
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
      
        
        return set.contains(value);
    }
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * boolean param_2 = obj.find(value);
 */