Two sums (Leetcode)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Solution

fn two_sums(nums: &[i32], target: i32) -> Vec<usize> {
    let mut seen = HashMap::new();
 
    for (idx, &num) in nums.iter().enumerate() {
        // get the compliment
        let compliment = target - num;
 
        // check if that compliment exists in the map
        // if so, return it
        if let Some(&j) = seen.get(&compliment) {
            return vec![j, idx];
        }
 
        seen.insert(num, idx);
    }
 
    vec![]
}

Breakdown

We can use the hash table to keep track of indices of numbers we have already seen as we iterate through the array. This allows us to check, in constant time, whether the current number’s complement has appeared before.

let mut seen = HashMap::new();

As we loop through the array, we calculate the complement needed to reach the target value.

let complement = target - num;

Before inserting the current number into the hash table, we check whether its complement already exists. If it does, we have found the two indices that sum to the target.

if let Some(&j) = seen.get(&complement) {
    return vec![j, idx];
}

If the complement is not found, we store the current number along with its index in the hash table for future lookups.

seen.insert(num, idx);

This ensures that we do not reuse the same element twice, since we only ever match the current element with values seen earlier in the iteration.

Complexity Analysis

Time complexity: $O(n)$, where $n$ is the number of elements in the array. Each lookup and insertion into the hash table is $O(1)$ on average.

Space complexity: $O(n)$, due to the additional hash table used to store previously seen elements.

Final Thoughts

This is a classic example of how trading space for time can significantly improve performance. The naive approach using nested loops would run in $O(n²)$, while a hash based solution brings it down to linear time.