05 August 2008
Design and implement a TwoSum class. It should support the following operations: 1
add
1
find
1
add
1
find
Example 1:
1
2
3
add(1); add(3); add(5);
find(4) -> true
find(7) -> false
Example 2:
1
2
3
add(3); add(1); add(2);
find(3) -> true
find(6) -> false
这道题跟Array的关系不大，放在这里主要是跟kSum所有的题放在一起。
用1-2Sum里面HashMap的思路来解，add的话是O(1)，find的话需要遍历整个keyset，是O(n)，Space都是O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class TwoSum {
Map<Integer, Integer> map;//用一个HashMap来保存每次存进来的number的次数
/** Initialize your data structure here. */
public TwoSum() {
map = new HashMap<Integer, Integer>();//初始化map为HashMap
}
/** Add the number to an internal data structure.. */
public void add(int number) {
if (map.containsKey(number)) {
//如果number之前加入过，则次数+1，因为是2Sum，找两个数，所以map.get(number) + 1写成2也可以
map.put(number, map.get(number) + 1);
} else {
map.put(number, 1);//第一次加入
}
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
//这里对HashMap的keyset进行遍历，找到是否存在两个数相加等于value
Iterator<Integer> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
int num1 = iterator.next();
int num2 = value - num1;
if (map.containsKey(num2)) {//表示第二个数在HashMap中存在，之前加入过，可以考虑配对
if (num1 != num2 || map.get(num2) >= 2) {//如果两个数不同，肯定可以配对；或者如果两个数相同，第（一）二个数有两个或以上的出现次数，也可以配对，因为一个数不能配对
return true;
}
}
}
return false;
}
}
/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum obj = new TwoSum();
* obj.add(number);
* boolean param_2 = obj.find(value);
*/