Leetcode 170. Two Sum III - Data

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.

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

思路：自己是用了一个map和一个set，add的时候效率较低，get的时候效率高，提交后是tle。因为case中add操作多，get操作少，如果get中进行遍历的话是可以通过的。

HashMap<Integer, Integer> map = new HashMap<>();
HashSet<Integer> set = new HashSet<>();

public FN_TwoSumIII() {

}

/** Add the number to an internal data structure.. */
public void add(int number) {
    if (map.containsKey(number)) {
        if (map.get(number) > 1) {
            return;
        } else {
            map.put(number, 2);
            set.add(number*2);
        }
    } else {
        for (Integer num : map.keySet()) {
            set.add(num + number);
        }
        map.put(number, 1);
    }
}

/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
    return set.contains(value);
}

答案中还有一个方法很巧妙，每次get的时候判断判断target和当前遍历值的差值是否存在于map中。

private List<Integer> list = new ArrayList<Integer>();
private Map<Integer, 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;
        if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2))) return true;
    }
    return false;
}