Two Sum

Easy

The problem

Given a list of numbers and a target, find the two different positions whose numbers add up to the target, and return those two indices. You may return them in any order.

Example 1
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
nums[0] + nums[1] = 2 + 7 = 9.
Example 2
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
nums[1] + nums[2] = 2 + 4 = 6. (3 + 3 would reuse the same position, which is not allowed.)
Example 3
Input: nums = [3, 3], target = 6
Output: [0, 1]
Two different positions can hold equal numbers.

Limits

2 ≤ nums.length ≤ 100,000
Exactly one pair of positions adds up to target
You cannot use the same position twice

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

For each number x, which exact value would complete the pair? Can you find it without scanning again?

The idea

Walk the array; for each x look up target−x in a map of value→index; if missing, store x with its index.

Target: O(n) time, O(n) space

Go function shape

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

Reference solution

Tested with go test. Try it yourself first, then compare.

// TwoSum: indices of the two numbers that add up to target.
// Remember each value's index; the complement is what we look up.
func TwoSum(nums []int, target int) []int {
	seen := map[int]int{}
	for i, v := range nums {
		if j, ok := seen[target-v]; ok {
			return []int{j, i}
		}
		seen[v] = i
	}
	return nil
}

Read the lesson: Arrays & Hash Map