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。因?yàn)閏ase中add操作多汰规，get操作少，如果get中進(jìn)行遍歷的話是可以通過的物邑。
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和當(dāng)前遍歷值的差值是否存在于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;
}