# 167. Two Sum II - Input Array Is Sorted

## 題目敘述

Given a 1-indexed array of integers `numbers` that is already sorted in non-decreasing order, find two numbers such that they add up to a specific `target` number. Let these two numbers be `numbers[index1]` and `numbers[index2]` where `1 <= index1 < index2 <= numbers.length`.

Return the indices of the two numbers, `index1` and `index2`, added by one as an integer array `[index1, index2]` of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

``````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. We return [1, 2].
``````

Example 2:

``````Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
``````

Example 3:

``````Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
``````

Constraints:

• `2 <= numbers.length <= 3 * 10**4`
• `-1000 <= numbers[i] <= 1000`
• `numbers` is sorted in non-decreasing order.
• `-1000 <= target <= 1000`
• The tests are generated such that there is exactly one solution.

## 解法解析

Time complexity: `O(n)` Space complexity: `O(1)`

### 解法範例

#### Go

``````func twoSum(numbers []int, target int) []int {
var (
low  int = 0
high int = len(numbers) - 1
)
for low < high {
total := numbers[low] + numbers[high]
if total == target {
return []int{low + 1, high + 1}
}
if total < target {
low++
} else {
high--
}
}
return []int{-1, -1}
}
``````

#### JavaScript

``````/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
let low = 0,
high = numbers.length - 1;
while (low < high) {
const sum = numbers[low] + numbers[high];
if (sum === target) {
return [low + 1, high + 1];
}
if (sum < target) {
low++;
} else {
high--;
}
}
return [-1, -1];
};
``````

#### Kotlin

``````class Solution {
fun twoSum(numbers: IntArray, target: Int): IntArray {
var low = 0
var high = numbers.size - 1
while (low < high) {
val sum = numbers[low] + numbers[high]
if (sum == target) {
return intArrayOf(low + 1, high + 1)
}
if (sum < target) {
low++
} else {
high--
}
}
return intArrayOf(-1, -1)
}
}
``````

#### PHP

``````class Solution
{

/**
* @param Integer[] \$numbers
* @param Integer \$target
* @return Integer[]
*/
function twoSum(\$numbers, \$target)
{
\$low = 0;
\$high = count(\$numbers) - 1;
while (\$low < \$high) {
\$sum = \$numbers[\$low] + \$numbers[\$high];
if (\$sum == \$target) {
return [\$low + 1, \$high + 1];
}
if (\$sum < \$target) {
\$low++;
} else {
\$high--;
}
}
return [-1, -1];
}
}
``````

#### Python

``````class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
low: int = 0
high: int = len(numbers) - 1
while low < high:
total: int = numbers[low] + numbers[high]
if total == target:
return [low + 1, high + 1]
if total < target:
low += 1
else:
high -= 1
return [-1, -1]
``````

#### Rust

``````impl Solution {
pub fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
let mut low = 0;
let mut high = numbers.len() - 1;
while low < high {
let sum = numbers[low]+numbers[high];
if sum == target {
return Vec::from([low as i32 + 1, high as i32 + 1]);
}
if sum < target {
low+=1;
} else {
high-=1;
}
}
return Vec::from([-1, -1]);
}
}
``````

#### Swift

``````class Solution {
func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
var low: Int = 0
var high: Int = numbers.count - 1
while low < high {
let sum: Int = numbers[low] + numbers[high]
if sum == target {
return [low + 1, high + 1]
}
if sum < target {
low += 1
} else {
high -= 1
}
}

return [-1, -1]
}
}
``````

### Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!