170. Two Sum III - Data structure design

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 5 * 104 calls will be made to add and find.

Rust Solution

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);
}

Having problems with this solution? Click here to submit an issue on github.