1. Two Sum

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

Problem Summary

Find two numbers in an array whose sum equals the given value, and return the indices of the two numbers in the array.

Solution Approach

The optimal time complexity for this problem is O(n).

Scan the array in order. For each element, look in the map for the other half of the number that can combine with it to make the given value. If it is found, directly return the indices of the two numbers. If it is not found, store this number in the map and wait until the “other half” number is encountered, then retrieve it and return the result.

Code

package leetcode

func twoSum(nums []int, target int) []int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		another := target - nums[i]
		if index, ok := m[another]; ok {
			return []int{index, i}
		}
		m[nums[i]] = i
	}
	return nil
}