描述
設(shè)計b并實現(xiàn)一個 TwoSum 類泉手。他需要支持以下操作:add 和 find压昼。
add -把這個數(shù)添加到內(nèi)部的數(shù)據(jù)結(jié)構(gòu)宙项。
find -是否存在任意一對數(shù)字之和等于這個值
樣例
add(1);add(3);add(5);
find(4) //返回true
find(7) //返回false
思路
要考慮比如 3 + 3 = 6鲸阻，兩個 3 是不是同一個數(shù)切诀，3 的出現(xiàn)次數(shù)
代碼
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) {
// 統(tǒng)計同一數(shù)字出現(xiàn)的次數(shù)
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 到底是不是同一個數(shù)斜纪，是不同的 return true
if (num1 == num2 && map.get(num1) > 1) {
return true;
} else if (num1 != num2 && map.containsKey(num2)) {
return true;
}
}
return false;
}
}
