双指针
数组已经按非递减顺序排列，这个有序性质正好可以利用起来。
设左指针 $left$ 指向最小值，右指针 $right$ 指向最大值。若两数之和小于 $target$，说明当前和偏小，需要让左指针右移来增大和；若两数之和大于 $target$，说明当前和偏大，需要让右指针左移来减小和。这样每次都能排除一部分不可能的情况。
由于题目保证恰好存在一个答案，因此当两数之和等于 $target$ 时，直接返回对应下标即可。注意题目下标从 $1$ 开始，所以最终答案需要加一。
时间复杂度 $O(n)$
空间复杂度 $O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[]{left + 1, right + 1};
}
}
|