Two Sum

Given an array of integers and a target, return the indices of the two numbers that add up to the target.

TimeO(n)

SpaceO(n)

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

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

Constraints

Input: line 1 — space-separated integers; line 2 — target integer.
Output: print two indices separated by a space on one line (once per approach in the reference solution).
Answer rule: return [i, j] where i < j is not required — any valid order of the two indices is accepted.
Exactly one solution is guaranteed.

Input

2 7 11 15
9

Output

0 1

Explanation: nums[0] + nums[1] = 2 + 7 = 9.

Naive Solution

Try every unordered pair (i, j) where i < j. If nums[i] + nums[j] == target, return [i, j].

Two nested loops — no extra storage, but quadratic comparisons.

// Compare every unordered pair (i, j) where i < j.
// Time: O(n²)  Space: O(1)
fn sum_pair_naive(numbers: &[i64], target: i64) -> Vec<usize> {
    let numbers_length: usize = numbers.len();
    if numbers_length < 2 {
        return vec![];
    }
 
    for f_idx in 0..numbers_length - 1 {
        for s_idx in (f_idx + 1)..numbers_length {
            if numbers[f_idx] + numbers[s_idx] == target {
                return vec![f_idx, s_idx];
            }
        }
    }
    vec![]
}

Time — O(n²)

Roughly n(n−1)/2 pair checks in the worst case.

Space — O(1)

Only index variables — no auxiliary collection.

Time: for n = 1,000, ~500,000 comparisons. Most pairs are checked even though only one answer exists.

Space: O(1), but time is quadratic.

Next step: remember each value's index in a hash table so complement lookup is O(1).

Two-Pass Solution

Pass 1: build num_to_index — map each value to its index.
Pass 2: for each idx, compute complement = target - nums[idx].
- If complement is in the map and num_to_index[complement] != idx, return [idx, num_to_index[complement]].

The != idx guard prevents using the same element twice (important when duplicates exist).

// Pass 1: map each value to its index. Pass 2: hunt for target − num.
// Time: O(n)  Space: O(n)
fn sum_pair_two_pass_hash_table(numbers: &[i64], target: i64) -> Vec<usize> {
    let numbers_length: usize = numbers.len();
    if numbers_length < 2 {
        return vec![];
    }
 
    let mut num_to_index: HashMap<i64, usize> = HashMap::new();
    for (idx, &num) in numbers.iter().enumerate() {
        num_to_index.insert(num, idx);
    }
 
    for (idx, &num) in numbers.iter().enumerate() {
        let complement = target - num;
        if let Some(&comp_idx) = num_to_index.get(&complement) {
            if comp_idx != idx {
                return vec![idx, comp_idx];
            }
        }
    }
    vec![]
}

Time — O(n)

Pass 1: O(n) to build the map. Pass 2: another O(n) scan → O(n) total.

Space — O(n)

The hash map stores up to n value → index entries.

Tradeoff: linear time, but the array is walked twice. Can we find the pair in a single pass?

Optimal Solution

Walk the array once with index i:

Compute complement = target - nums[i].
If complement is already in num_to_index, return [num_to_index[complement], i].
Otherwise store num_to_index[nums[i]] = i.

Check before insert so the same element is never paired with itself.

// Single pass: check complement before inserting the current value.
// Time: O(n)  Space: O(n)
fn sum_pair_one_pass_hash_table(numbers: &[i64], target: i64) -> Vec<usize> {
    let numbers_length: usize = numbers.len();
    if numbers_length < 2 {
        return vec![];
    }
 
    let mut num_to_index: HashMap<i64, usize> = HashMap::new();
    for (idx, &num) in numbers.iter().enumerate() {
        let complement = target - num;
        if let Some(&comp_idx) = num_to_index.get(&complement) {
            return vec![comp_idx, idx];
        }
        num_to_index.insert(num, idx);
    }
    vec![]
}

Time — O(n)

Single pass; each hash map lookup and insert is O(1) average → O(n) total.

Space — O(n)

The map holds up to n entries before the answer is found.

Result: same correctness as naive and two-pass, with one scan instead of two.

Full source: Rust · Python