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
5 * 104
calls will be made to add
and find
.use std::collections::HashMap;
use std::i32;
#[derive(Default)]
struct TwoSum {
numbers: HashMap<i32, usize>,
max: i32,
min: i32,
}
impl TwoSum {
fn new() -> Self {
TwoSum {
numbers: HashMap::new(),
max: i32::MIN,
min: i32::MAX,
}
}
fn add(&mut self, number: i32) {
self.max = i32::max(self.max, number << 1);
self.min = i32::min(self.min, number << 1);
self.numbers
.insert(number, self.numbers.get(&number).unwrap_or(&0) + 1);
}
fn find(&self, value: i32) -> bool {
if value < self.min || value > self.max {
return false;
}
for (&a, &v) in &self.numbers {
let b = value - a;
if a == b && v == 2 {
return true;
}
if a != b && self.numbers.contains_key(&b) {
return true;
}
}
false
}
}
#[test]
fn test() {
let mut two_some = TwoSum::new();
two_some.add(1);
two_some.add(3);
two_some.add(5);
let value = 4;
let res = true;
assert_eq!(two_some.find(value), res);
let value = 7;
let res = false;
assert_eq!(two_some.find(value), res);
}