Two Sum

Easy

Array

Hash Table

Description

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.

Constraints

\[\begin{flalign} & \bullet\quad 2 \le \text{nums.length} \le 10^4 \\ & \bullet\quad -10^9 \le \text{nums[i]} \le 10^9 \\ & \bullet\quad -10^9 \le \text{target} \le 10^9 \\ & \bullet\quad \text{Only one valid answer exists.} & \end{flalign}\]

Function

struct Solution;

impl Solution {
    pub fn two_nums(nums: Vec<i32>, target: i32) -> Vec<i32> {}
}

Examples

Example 1:

Input: nums = [2, 4, 6, 8], target = 12
Output: [1, 3] or [3, 1]
Explanation: nums[1] + nums[3] = 4 + 8 = 12. (target = 12)

Example 2:

Input: nums = [1, 1, 2, 2], target = 2
Output: [0, 1] or [1, 0]
Explanation: nums[0] + nums[1] = 1 + 1 = 2. (target = 2)

Solutions

Brute-Force Double Loop

We iterate every integer inside the array nums, denoted as nums[i]. For each nums[i], we then iterate the array again and try to find another integer nums[j] that makes: $nums[i] + nums[j] = target$. If found, we return their indices [i, j] or [j, i].

struct Solution;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for i in 0..nums.len() {
            for j in i+1..nums.len() {
                if nums[i] + nums[j] == target{
                    return vec![i as i32, j as i32];
                }
            }
        }
        vec![]  // return empty if no pair found
    }
}

Code Analysis

Line 3 to Line 9: Outer loop block. The pointer i iterates array nums from beginning (index = $0$) to the end (index = $\text{the length of array} - 1$).
Line 4 to Line 8: Inner loop block. The pointer j iterates array nums from the next index of i (index = $i + 1$) to the end (index = $\text{the length of array} - 1$).
Line 5 to Line 7: If condition block. If the sum of two numbers (where pointers i and j pointed to) is equal to target, return the two indices. Since the return types is defined as Vec<i32>, we need to convert the usize (original type of i and j ) to i32.

Performance Analysis

Time Complexity:

For each element nums[i], we compare it with all later elements nums[j]:
\[T(n) = \sum\limits_{i=0}^{n-1} (n-1-i) = \frac{n(n-1)}{2} = \Theta{(n^2)}\]
- Average: $\Theta{(n^2)}$
- Worst: $\mathcal{O}(n^2)$ <– Not found or found at last two elements […, x, target - x]
- Best: $\Omega{(1)}$ <– Found at fist two elements [x, target - x, …]
Space Complexity:
- Uses only constant extra variables (i, j).
- No auxiliary data structures.
\[S(n) = \mathcal{O}(1)\]
Note:

nums is passed by value (moved), but we do not clone its contents, so no extra heap allocation proportional to n.

Heap-Map Single Pass

The Brute Force Double Loop approach is inefficient because for every number $\text{nums}[i]$, the inner pointer $j$ redundantly scans the rest of the array to find the required complement, $\text{target} - \text{nums}[i]$. This repeated searching significantly slows down the process.

We can eliminate the need for the second pointer, $j$, by leveraging space for speed (Time-Space Tradeoff).

As we iterate through the array with pointer $i$, we “look back” into a hash map (or dictionary) for the complement we need: $\text{complement} = \text{target} - \text{nums}[i]$.
If the complement exists in the hash map, we immediately found the solution and return the current index $i$ and the stored index of the complement.
If the complement is not found, we store the current number $\text{nums}[i]$ and its index $i$ into the hash map. This prepares the map for any subsequent number that might need $\text{nums}[i]$ as its complement.

By making $i$ “smarter” and using the hash map as a memory of past visits, we achieve a significant time complexity improvement from $\Theta(n^2)$ to $\Theta(n)$.

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut hm = HashMap::new();
        for i in 0..nums.len() {
            let cmpl = target - nums[i];
            if let Some(&j) = hm.get(&cmpl) {
                return vec![i as i32, j as i32];
            }
            hm.insert(nums[i], i);
        }
        vec![]
    }
}

Code Analysis

Line 5: Create an empty hash table for storing (integer, index) later.
Line 6 to Line 12: Loop block. The pointer i iterates array nums. Inside this loop, it computes complement number $\text{target} - nums[i]$, searches the complement number inside hash map, and inserts current record (nums[i], i) for future use when necessary.
Line 8 to Line 10: If condition block. If nums[i]’s complement number is found in hashmap, we know $\text{complement} + nums[i] = target$. Thus, we retrieve the index of the complement number, denoted as j, and then return the two indices [i, j]. Since the return types is defined as Vec<i32>, we need to convert the usize (original type of i and j ) to i32.

Performance Analysis

Time Complexity:

Each iteration does two main operations:
- hm.get() –> $\Theta(1)$
- hm.insert() –> $\Theta(1)$
Therefore:
\[T(n) = \Theta{(n)}\]
- Average: $\Theta{(n)}$
- Worst: $\mathcal{O}(n^2)$ <– If all keys hash-collide (theoretical, extremely rare).
- Best: $\Omega{(1)}$ <– Found complement immediately.
Space Complexity:
- Uses only constant extra variables (i, cmpl).
- The hash map stores at most n key-value pairs.
\[S(n) = \mathcal{O}(n)\]
Note:

Each entry stores a 32-bit key (i32) and a 64-bit index (usize), plus internal hash-table overhead (buckets, load factor, etc.).