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