170. Two Sum III - Data structure design

https://leetcode.com/problems/two-sum-iii-data-structure-design/description/

image.png

这道题是一个TRADE OFF，要么用O N add, 要么 O N find.
另一个就是 O 1 操作了。

如果需要O 1 find，那么在加的时候，就把新来的每个数，都和之前的数加好，存进一个SET，这样取就是O1了

如果想加O 1，那么FIND就是基本的2 sum.
O1 find

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

o1 add

class TwoSum {
    List<Integer> a;
    /** Initialize your data structure here. */
    public TwoSum() {
        a = new ArrayList<>();
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        a.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        Set<Integer> s = new HashSet<>();
        for(int i : a){
            if(s.contains(value-i)) return true;
            s.add(i);
        }
        return false;
    }
}