170两数之和III-数据结构设计.md

170. 两数之和 III - 数据结构设计

class TwoSum {

    private ArrayList<Integer> list;
    private boolean sorted = false;

    /** Initialize your data structure here. */
    public TwoSum() {
        list = new ArrayList<>();
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        list.add(number);
        this.sorted = false;
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        //减少排序的次数
        if(!this.sorted) {
            Collections.sort(this.list);
            this.sorted = true;
        }
        return twoSumExist(this.list, value);
    }

    private boolean twoSumExist(List<Integer> list, int target) {
        int l = 0;
        int r = list.size() - 1;
        while(l < r) {
            int cur = list.get(l) + list.get(r);
            if(cur > target) {
                r--;
            } else if(cur < target) {
                l++;
            } else {
                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);
 */