-
Notifications
You must be signed in to change notification settings - Fork 2
/
TwoSumDesign.java
74 lines (65 loc) · 1.89 KB
/
TwoSumDesign.java
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
package Leetcode;
import java.util.HashMap;
import java.util.Map;
/**
* @author kalpak
*
* 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.
*
* Example 1:
*
* add(1); add(3); add(5);
* find(4) -> true
* find(7) -> false
*
* Example 2:
*
* add(3); add(1); add(2);
* find(3) -> true
* find(6) -> false
*
*/
public class TwoSumDesign {
/** Initialize your data structure here. */
Map<Integer, Boolean> map;
int minVal = Integer.MAX_VALUE;
int maxVal = Integer.MIN_VALUE;
public TwoSumDesign() {
map = new HashMap<>();
}
/** Add the number to an internal data structure.. */
public void add(int number) {
map.put(number, map.containsKey(number));
minVal = Math.min(minVal, number);
maxVal = Math.max(maxVal, number);
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
// check if the value is at all possible
if(value < minVal*2 || value > maxVal*2)
return false;
/**
* Consider value = 6.
* If key = 3 and there were two entries of 3,
* then diff = 3 and map.get(3) will be true.
*
* Else, if key = 4, and diff = 2.
* we need to check if the map contains 2 along with diff != key
*/
for(int key : map.keySet()) {
int diff = value - key;
if(map.containsKey(diff) && (key != diff || map.get(diff) == true))
return true;
}
return false;
}
public static void main(String[] args) {
TwoSumDesign obj = new TwoSumDesign();
obj.add(1);
obj.add(3);
System.out.println(obj.find(4));
}
}