给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
codeType
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
codeType
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
codeType
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示：
- 2 <= numbers.length <= 3 * 104
- -1000 <= numbers[i] <= 1000
- numbers 按 非递减顺序 排列
- -1000 <= target <= 1000
- 仅存在一个有效答案
解法一：二分查找
时间复杂度O(nlogn)
ts
function twoSum(numbers: number[], target: number): number[] {
// 用暴力法的话就把所有组合都试一遍
// 因为数组是按非递减顺序排列，所以可以用二分查找
// 只要先固定一个数，然后用二分查找找差值即可，查找过程时间复杂度是O(logn)
// 每个数都要固定一遍，所以是O(n),总的就是O(nlogn)
let i=0 // 固定数的索引
const n = numbers.length
while(i < n-1){
let low = i + 1, high = n - 1 // i本身不能包括到查找范围
const diff = target - numbers[i]
while(low <= high){
const center = Math.floor((low + high) / 2)
if(numbers[center] === diff){
return [i + 1, center + 1] // 返回的是下标，要+1
}else if(numbers[center] < diff){ // 在右半边
low = center + 1
}else{ // 在左半边
high = center - 1
}
}
i++
}
};
解法二：双指针
初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。
时间复杂度是O(n)
ts
function twoSum(numbers: number[], target: number): number[] {
// 双指针法
const n = numbers.length
let i = 0, j = n - 1
while(i<j){
if(numbers[i] + numbers[j] === target){
return [i + 1, j + 1]
}else if(numbers[i] + numbers[j] < target){
i++
}else{
j--
}
}
};