今日中等題：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

一般這種排序后的題目，就是讓你用二分法或者雙指針，但是壞習(xí)慣是開(kāi)始就想先爆破，所以最開(kāi)始就是暴力法，先雙重遍歷，果然超時(shí)了。

這個(gè)時(shí)候開(kāi)始考慮優(yōu)化算法，二分法的思路是，先找到第一個(gè)數(shù)，然后用target減去它，去找第二個(gè)數(shù)。

但是雙指針更簡(jiǎn)單，一次遍歷即可，因?yàn)槭怯行驍?shù)組，從頭尾開(kāi)始找就行：

1. 和小于target的，說(shuō)明頭小了，要右移；
2. 和大于target的，說(shuō)明尾大了，要左移；
3. 和等于target的，恭喜你找到了，返回下標(biāo)就行，但是這里要注意，題目下標(biāo)是從1開(kāi)始，所以還要記得+1；

看下兩種解法：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        /** 暴力法：全遍歷，O(n*n)，超時(shí)了:(
        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;
    }
}