# Rust Interview Puzzles: Find a pair with a given sum in a vector

·

### Problem

In an unsorted vector `vec` of numbers we need to find any pair (`Tuple`) with a provided `sum`.

#### Example 1:

Input: `vec = [8, 7, 2, 5, 3, 1]`, `sum = 10`
Output: `(2, 8)`

#### Example 2:

Input: `vec = [5, 2, 6, 8, 6, 9]`, `sum = 12`
Output: `(6, 6)`

#### Example 3:

Input: `vec = [5, 2, 6, 8, 1, 9]`, `sum = 12`
Output: `None`

### Solution

``````fn find_pair_with_given_sum(vec: &Vec<i32>, sum: i32) -> Option<(i32, i32)> {
let mut set = HashSet::new();

for e in vec {
let another = sum - e;
match set.get(&another) {
Some(_) => return Some((*e, another)),
_ => {
set.insert(e);
}
}
}

return None;
}
``````

### Explanation

We iterate over elements in the vector `vec` and for each element `e` try to find `sum - e` element in the created earlier HashSet `set`. If we could not find `sum - e` in the set, then we just add the element `e` to the `set`. If we've found `sum - e` in the `set`, then we immediately return `(e, sum - e)` as the found pair. If we've iterated over the entire vector and didn't find a pair, then we just return `None`.

### Complexity

The time complexity of this solution is `O(n)` (`n` is a size of the input vector). Also the solution requires `O(n)` extra space for the `HashSet` we created.

Rust Playground with this code