Two Sum

Problem

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

Each input has exactly one solution, and you may not use the same element twice.

Intuition

The obvious approach is a double loop: for every pair (i, j), check if nums[i] + nums[j] == target. That's O(n²) — and it does far more work than necessary.

Here's the reframe. For each value x, the complement we need is fully determined: need = target - x. The question stops being "do any two numbers sum to target?" and becomes "have I already seen need?"

Answering that question in constant time is what a HashMap is for. As we walk the array, we keep a map of value → index for every number seen so far. The nested search collapses into a single pass.

This is the most fundamental pattern in algorithmic thinking: trade space for time with a lookup table. You will reuse it for the rest of your career.

Approach

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];
                }
            }
        }
        unreachable!("no valid pair found");
    }
}

function twoSum(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  throw new Error("no valid pair found");
}

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut seen: HashMap<i32, i32> = HashMap::with_capacity(nums.len());

        for (i, &x) in nums.iter().enumerate() {
            let need = target - x;
            if let Some(&j) = seen.get(&need) {
                return vec![j, i as i32];
            }
            seen.insert(x, i as i32);
        }

        unreachable!("no valid pair found");
    }
}

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();

  for (let i = 0; i < nums.length; i++) {
    const need= target - nums[i];
    const j= seen.get(need);
    if (j = undefined) return [j, i];
    seen.set(nums[i], i);
  }

  throw new Error("no valid pair found");
}

Trace

Walking the HashMap approach through nums = [2, 7, 11, 15] with target = 9:

Two iterations. One allocation. The map never grows past one entry before we return.

Edge cases

• Duplicate values where x + x == target — e.g. nums = [3, 3], target = 6. The check-before-insert ordering handles this: on i = 1, the value 3 from index 0 is already in the map.
• Negative numbers — arithmetic is signed. No special handling needed.
• No solution exists — the problem statement rules this out. If your production variant could see it, return Option<Vec<i32>> / number[] | null and remove the unreachable! / throw.

Takeaway

Whenever you see a brute force that asks "does there exist an x such that…?" inside a loop, ask: can I precompute that question into a HashMap or HashSet?

That single reflex unlocks dozens of problems on this roadmap — #217 Contains Duplicate, #242 Valid Anagram, #49 Group Anagrams, #128 Longest Consecutive Sequence all reduce to the same trade.

The pattern scales beyond leetcode. Every time you build a feature and find yourself scanning a list to answer the same question repeatedly, you're looking at the same transformation: index the data once, answer queries forever.