今日中等題：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
一般這種排序后的題目阶剑，就是讓你用二分法或者雙指針七咧，但是壞習(xí)慣是開始就想先爆破栅隐，所以最開始就是暴力法，先雙重遍歷卑雁，果然超時了楷兽。
這個時候開始考慮優(yōu)化算法异雁，二分法的思路是，先找到第一個數(shù)，然后用target減去它肤舞，去找第二個數(shù)紫新。
但是雙指針更簡單，一次遍歷即可李剖，因為是有序數(shù)組芒率，從頭尾開始找就行：
- 和小于target的，說明頭小了篙顺，要右移偶芍；
- 和大于target的，說明尾大了德玫，要左移匪蟀；
- 和等于target的，恭喜你找到了宰僧，返回下標(biāo)就行材彪，但是這里要注意，題目下標(biāo)是從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;
// 優(yōu)化方案：雙指針穗泵，一次遍歷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;
}
}
