Description#
Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.
Implement the TwoSum class:
TwoSum() Initializes the TwoSum object, with an empty array initially.void add(int number) Adds number to the data structure.boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.
Example 1:
Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]
Explanation
TwoSum twoSum = new TwoSum();
twoSum.add(1); // [] --> [1]
twoSum.add(3); // [1] --> [1,3]
twoSum.add(5); // [1,3] --> [1,3,5]
twoSum.find(4); // 1 + 3 = 4, return true
twoSum.find(7); // No two integers sum up to 7, return false
Constraints:
-105 <= number <= 105-231 <= value <= 231 - 1- At most
104 calls will be made to add and find.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class TwoSum:
def __init__(self):
self.cnt = Counter()
def add(self, number: int) -> None:
self.cnt[number] += 1
def find(self, value: int) -> bool:
for x, v in self.cnt.items():
y = value - x
if y in self.cnt:
if x != y or v > 1:
return True
return False
# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)
# param_2 = obj.find(value)
|
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
| class TwoSum {
private Map<Integer, Integer> cnt = new HashMap<>();
public TwoSum() {
}
public void add(int number) {
cnt.merge(number, 1, Integer::sum);
}
public boolean find(int value) {
for (var e : cnt.entrySet()) {
int x = e.getKey(), v = e.getValue();
int y = value - x;
if (cnt.containsKey(y)) {
if (x != y || v > 1) {
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);
*/
|
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
| class TwoSum {
public:
TwoSum() {
}
void add(int number) {
++cnt[number];
}
bool find(int value) {
for (auto& [x, v] : cnt) {
long y = (long) value - x;
if (cnt.count(y)) {
if (x != y || v > 1) {
return true;
}
}
}
return false;
}
private:
unordered_map<int, int> cnt;
};
/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum* obj = new TwoSum();
* obj->add(number);
* bool param_2 = obj->find(value);
*/
|
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
| type TwoSum struct {
cnt map[int]int
}
func Constructor() TwoSum {
return TwoSum{map[int]int{}}
}
func (this *TwoSum) Add(number int) {
this.cnt[number]++
}
func (this *TwoSum) Find(value int) bool {
for x, v := range this.cnt {
y := value - x
if _, ok := this.cnt[y]; ok && (x != y || v > 1) {
return true
}
}
return false
}
/**
* Your TwoSum object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(number);
* param_2 := obj.Find(value);
*/
|
