給定一個(gè)已按照升序排列 的有序數(shù)組剔交，找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)搂捧。

函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值 index1 和 index2浑此，其中 index1 必須小于index2蚯妇。

說(shuō)明:

返回的下標(biāo)值（index1 和 index2）不是從零開(kāi)始的是趴。
你可以假設(shè)每個(gè)輸入只對(duì)應(yīng)唯一的答案涛舍，而且你不可以重復(fù)使用相同的元素。
示例:

輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標(biāo)數(shù) 9 唆途。因此 index1 = 1, index2 = 2 富雅。

解法1

暴力解法
雙層遍歷，時(shí)間復(fù)雜度為 O(n^2)肛搬，暴力解法沒(méi)有充分利用原數(shù)組的性質(zhì) —— 有序没佑，本文不采用。

當(dāng)我們看到數(shù)列有序的時(shí)候温赔，就應(yīng)該想到可以用二分搜索法蛤奢。

解法2

根據(jù)不同情況進(jìn)行分析，確定要遍歷的起始點(diǎn)陶贼，向中間靠攏對(duì)比啤贩，從而找到兩個(gè)下標(biāo)。

C++1

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int num = numbers.size();
        vector<int> index;
        int start, p;
        if(numbers.at(num-1) < target){
            start = num-1;
        }
        else if(numbers.at(num/2) < target&&target>0){
            start = num/2;
        }
        else if(target <= 0){
            int m;
            for(int k=0;k<num;k++){
                if(numbers.at(k) >= target){
                    m = k;
                    break;
                }
            }
            for(int p=m;p<num;p++){
                for(int u=p-1;u>=0;u--){
                    if(numbers.at(p) + numbers.at(u) == target){
                        index.push_back(u+1);
                        index.push_back(p+1);
                        return index;
                    }
                }
            }
        }
        else{
            p = num/2;
            while(numbers.at(p) > target){
                --p;
            }
            start = p;
        }
        
        for(int j=start;j<num;j++){
                for(int i=j-1;i>=0;i--){
                    if(numbers.at(i) + numbers.at(j) == target){
                        index.push_back(i+1);
                        index.push_back(j+1);
                        return index;
                    }
                }
        }
        for(int j=start;j>=0;j--){
                for(int i=j-1;i>=0;i--){
                    if(numbers.at(i) + numbers.at(j) == target){
                        index.push_back(i+1);
                        index.push_back(j+1);
                        return index;
                    }
                }
        }
        return index;
    }
};

解法3 對(duì)撞指針?lè)?/h4>

首先判斷首尾兩項(xiàng)的和是不是 target拜秧，如果比 target 小痹屹，那么我們左邊 (i)+1 位置的數(shù)（比左邊位置的數(shù)大）再和右相相加，繼續(xù)判斷枉氮。如果比 target 大志衍，那么我們右邊 (j)-1 位置的數(shù)（比右邊位置的數(shù)小）再和左相相加聊替，繼續(xù)判斷楼肪。我們通過(guò)這樣不斷放縮的過(guò)程，就可以在 O(n) 的時(shí)間復(fù)雜度內(nèi)找到對(duì)應(yīng)的坐標(biāo)位置佃牛。

python3

class Solution:
    def twoSum(self, numbers, target):
        n = len(numbers)
        if (n < 2):
            return []
        i = 0
        j = n-1
        while i < j:
            if numbers[i] + numbers[j] == target:
                return [i+1,j+1]
            elif numbers[i] + numbers[j] < target:
                i += 1
            else:
                j -= 1
        return []

妙啊