-
Notifications
You must be signed in to change notification settings - Fork 0
/
TwoSum3.java
51 lines (44 loc) · 1.52 KB
/
TwoSum3.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
import java.util.*;
/*
* Two Sum III – Data structure design
* Design and implement a TwoSum class. It should support the following operations: add
* and find.
* add(input) – Add the number input to an internal data structure.
* find(value) – 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;
* possible solutions for this problem
*
* 1. if find(value) >>> add(input) operations then
* for each add operations, calculate all 2 sums and store them in hash map
* Space complexity - O(n^2) for storing all sums, O(n) for storing the inputs
* Time complexity - add(input) : O(n), find(value) : O(1)
* 2. using binary search, maintaining sorted order of the input
* Space complexity - O(n)
* Time complexity - add(input) : O(logn), find(value) : O(n)
* 3. using hashtable,
* Space complexity - O(n)
* Time complexity - add(input) : O(1), find(value) : O(n)
*
*/
class TwoSum3 {
HashMap<Integer, Integer> map = new HashMap<>();
public void add(int input){
int count = map.containsKey(input) ? map.get(key) : 0;
map.put(input,count+1);
}
public boolean find(int value){
for(Map.Entry<Integer, Integer> entry: map.entrySet()){
int num = entry.getKey();
int y = value - num;
if(y == num){
if(entry.getValue() >=2)
return true;
} else if(map.contains(y)){
return true;
}
}
return false;
}
}