167. Two Sum II - Input array is sorted #

Problem #

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• Your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Problem Summary #

Find two numbers whose sum equals target, and output their indices. Note that the same number cannot be used twice. Output the indices in ascending order. It is assumed that the problem always has one solution.

Solution Approach #

This problem is even simpler than Problem 1, Two Sum, because the array here is sorted. You can directly use the solution from the first problem to solve this problem.

Code #

package leetcode

// Solution 1 This problem can make use of the sorted property of the array
func twoSum167(numbers []int, target int) []int {
	i, j := 0, len(numbers)-1
	for i < j {
		if numbers[i]+numbers[j] == target {
			return []int{i + 1, j + 1}
		}
		if numbers[i]+numbers[j] < target {
			i++
		} else {
			j--
		}
	}
	return nil
}

// Solution 2 Regardless of whether the array is sorted, the space complexity is O(n) more than the previous solution
func twoSum167_1(numbers []int, target int) []int {
	m := make(map[int]int)
	for i := 0; i < len(numbers); i++ {
		another := target - numbers[i]
		if idx, ok := m[another]; ok {
			return []int{idx + 1, i + 1}
		}
		m[numbers[i]] = i
	}
	return nil
}