今日中等题：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
一般这种排序后的题目，就是让你用二分法或者双指针，但是坏习惯是开始就想先爆破，所以最开始就是暴力法，先双重遍历，果然超时了。
这个时候开始考虑优化算法，二分法的思路是，先找到第一个数，然后用target减去它，去找第二个数。
但是双指针更简单，一次遍历即可，因为是有序数组，从头尾开始找就行：
- 和小于target的，说明头小了，要右移；
- 和大于target的，说明尾大了，要左移；
- 和等于target的，恭喜你找到了，返回下标就行，但是这里要注意，题目下标是从1开始，所以还要记得+1；
看下两种解法：
class Solution {
public int[] twoSum(int[] numbers, int target) {
/** 暴力法：全遍历，O(n*n)，超时了:(
int head = 0;
int[] ans = new int[2];
while (head < numbers.length - 1) {
for (int tail = head+1; tail < numbers.length; tail++) {
if (numbers[head] + numbers[tail] == target) {
ans[0] = head + 1;
ans[1] = tail + 1;
return ans;
}
}
head++;
}
return ans;
*/
int head = 0;
int[] ans = new int[2];
int tail = numbers.length - 1;
// 优化方案：双指针，一次遍历O(n)
while (head < tail) {
if (numbers[head] + numbers[tail] == target) {
ans[0] = head + 1;
ans[1] = tail + 1;
return ans;
}
else if (numbers[head] + numbers[tail] < target) {
head++;
}
else {
tail--;
}
}
return ans;
}
}
