描述
设计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;
}
}
