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.

Function signature

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

Inputs / outputs

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

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

• Invariant: the map contains all values seen so far with their indices.
• The map counts/associations are updated consistently per element.
• Lookups use this exact state, so decisions are based on full prior data.
• Therefore the result is correct for the entire input.

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.

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.