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 theTwoSum
object, with an empty array initially.void add(int number)
Addsnumber
to the data structure.boolean find(int value)
Returnstrue
if there exists any pair of numbers whose sum is equal tovalue
, otherwise, it returnsfalse
.
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
5 * 104
calls will be made toadd
andfind
.
class TwoSum:
def __init__(self):
"""
Initialize your data structure here.
"""
self.counter = collections.Counter()
def add(self, number: int) -> None:
"""
Add the number to an internal data structure..
"""
self.counter[number] += 1
def find(self, value: int) -> bool:
"""
Find if there exists any pair of numbers which sum is equal to the value.
"""
for num in self.counter.keys():
other = value - num
if other in self.counter:
if other != num:
return True
if other == num and self.counter[num] > 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)
class TwoSum {
private Map<Integer, Integer> counter;
/** Initialize your data structure here. */
public TwoSum() {
counter = new HashMap<>();
}
/** Add the number to an internal data structure.. */
public void add(int number) {
counter.put(number, counter.getOrDefault(number, 0) + 1);
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
for (int num : counter.keySet()) {
int other = value - num;
if (counter.containsKey(other)) {
if (num != other) {
return true;
}
if (num == other && counter.get(other) > 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);
*/