Leetcode#167. Two Sum II - Input array is sorted

題目描述：給定一個升序排列的數組和另外一個數target，若數組中某兩個數的和等于target，輸出這兩個數的索引。假設隻有一個解，索引從1開始（注意不是從0開始）。

解題思路：雙指針問題。兩個指針，左指針在數組頭，右指針在數組尾。

• 若兩者之和等于target，則傳回索引；
• 若兩者之和大于target，則右指針左移；
• 若兩者之和小于target，則左指針右移；

C++實作如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        vector<int> ret(, -);

        //左指針
        int left = ;
        //右指針
        int right = numbers.size() - ;

        while(left < right)
        {
            int temp = numbers[left] + numbers[right];
            if(temp == target)
            {
                ret[] = left + ;
                ret[] = right + ;
                return ret;
            }
            else if(temp < target)
                left ++;
            else
                right --;
        }
    }
};
           

20180711更新

class Solution 
{
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        vector<int> ret;
        int length = numbers.size();
        int p = ;
        int q = length - ;
        while(p < q)
        {
            if(numbers[p] + numbers[q] > target)
                q--;
            else if(numbers[p] + numbers[q] < target)
                p++;
            else
            {
                ret.push_back(p + ); //務必加1
                ret.push_back(q + );
                break; //此時break，否則會逾時
            }
        }
        return ret;
    }
};