Two Sum

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

You may assume exactly one solution exists, and you may not use the same element twice.

Why this is worth learning

The map is a history of earlier positions. Looking up the complement before inserting the current value prevents one occurrence from pairing with itself.

Before coding: one-minute experiment

Why does [3,3], target 6 require lookup before insertion?

Function signature

func TwoSum(nums []int, target int) []int

Inputs / outputs

• nums: input slice of integers.
• target: target sum.
• Return: a slice of two distinct 0-based original indices [i, j], in either order.

Example

nums = [2,7,11,15], target = 9
Output: [0,1]

Constraints

• 2 <= len(nums) <= 100_000
• -1_000_000_000 <= nums[i], target <= 1_000_000_000
• Exactly one solution exists.

Core idea (near-solution)

Use a hash map from value to index. As you scan left to right, check if target - nums[i] has already appeared.

Invariant: the map contains all values seen so far with their indices.

Algorithm (step-by-step)

1. Create an empty map seen from value to index.
2. For each index i:
   • Compute need = target - nums[i].
   • If need is in the map, return [seen[need], i].
   • Otherwise store nums[i] -> i.

Correctness sketch

Before index i, seen contains a usable earlier index for every distinct value in nums[:i]. If target-nums[i] is present, that earlier index and i are distinct and their values sum to target, so the returned pair is valid. If absent, no earlier element can complete a pair ending at i. Inserting the current value then establishes the invariant for the next position. Any promised solution has a later endpoint, and its earlier value is present when that endpoint is processed, so the scan must find it. Replacing an earlier stored index for the same value preserves the existence of a usable distinct earlier partner.

Trace (hand walkthrough)

Example input:
nums = [2,7,11,15], target = 9
Output: [0,1]

Walk:
- i=0 val=2 -> need 7, store {2:0}
- i=1 val=7 -> need 2 found -> return [0,1]

Pitfalls to avoid

• Adding the current number before checking (can pick the same index).
• Returning 1-based indices by mistake.

Debugging lens

Check index distinctness, bounds, and sums. This version returns zero-based original indices and does not sort or mutate nums; TwoSumII has a different index convention.

Complexity

• Time: O(n)
• Extra space: O(n)

Implementation notes (Go)

• Check the complement before inserting the current value.
• Store value -> index in a map.

Reconstruction checkpoint

Why does [3,3], target 6 require lookup before insertion?

Return to Hash Map · Module quiz