描述

设计b并实现一个 TwoSum 类。他需要支持以下操作:add 和 find。
add -把这个数添加到内部的数据结构。
find -是否存在任意一对数字之和等于这个值

样例

add(1);add(3);add(5);
find(4) //返回true
find(7) //返回false
思路
要考虑比如 3 + 3 = 6，两个 3 是不是同一个数，3 的出现次数

代码

public class TwoSum {

    private List<Integer> list = null;
    private Map<Integer, Integer> map = null;
    public TwoSum() {
        list = new ArrayList<Integer>();
        map = new HashMap<Integer, Integer>();
    }

    // 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 i = 0; i < list.size(); i++) {
            int num1 = list.get(i), num2 = value - num1;
            // num1 = nums2 时，判断 num2 和 num1 到底是不是同一个数，是不同的 return true
            if (num1 == num2 && map.get(num1) > 1) {
                return true;
            } else if (num1 != num2 && map.containsKey(num2)) {
                return true;
            }
        }
        return false;
    }
}