Two Sum in Rust: three useful approaches

Given a list of integers and a target, return the indices of two values whose sum equals the target.

Start with the obvious solution

Checking every pair is easy to verify but takes O(n²) time:

fn two_sum_slow(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    for left in 0..nums.len() {
        for right in left + 1..nums.len() {
            if nums[left] + nums[right] == target {
                return Some((left, right));
            }
        }
    }
    None
}

Trade memory for speed

As we scan, a HashMap records each value's index. For the current value, we ask whether its complement has already appeared.

use std::collections::HashMap;

fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut seen = HashMap::new();

    for (index, &value) in nums.iter().enumerate() {
        if let Some(&other_index) = seen.get(&(target - value)) {
            return Some((other_index, index));
        }
        seen.insert(value, index);
    }

    None
}

The expected time is O(n) and the extra space is O(n).

A small Rust detail

The pattern &value copies each i32 out of the iterator's reference. Likewise, Some(&other_index) extracts a copied usize. For non-Copy values, we would need to think more carefully about borrowing or cloning.