0167. Two Sum I I Input Array Is Sorted

# 167. Two Sum II - Input array is sorted#

## 题目 #

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:

• 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.

``````

## 代码 #

``````
package leetcode

// 解法一 这一题可以利用数组有序的特性
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}
} else if numbers[i]+numbers[j] < target {
i++
} else {
j--
}
}
return []int{-1, -1}
}

// 解法二 不管数组是否有序，空间复杂度比上一种解法要多 O(n)
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 _, ok := m[another]; ok {
return []int{m[another] + 1, i + 1}
}
m[numbers[i]] = i
}
return nil
}

``````

Sep 6, 2020