题目描述

给定一个按升序排序的数组，请找出两个数，使得它们的和等于 $target$。

你的函数需要返回两个数的下标，两个下标不能相同，较小的下标在前，较大的下标在后。

注意：

1. 你返回的下标是从1开始的。
2. 数据保证有且仅有一组解。
3. 数组中的每个数仅能用一次。

样例

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2与7的和是9，它们的下标是1和2。

算法

(双指针扫描) $O(n)$

用两个指针 $i, j$ 分别从数组首尾往中间扫描，每次将 $i$ 后移一位，然后不断前移 $j$，直到 $numbers[i] + numbers[j] \le target$ 为止。如果 $numbers[i] + numbers[j] == target$，则找到了一组方案。

时间复杂度分析：两个指针总共将数组扫描一次，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0, j = numbers.size() - 1; i < j; i ++ )
        {
            while (numbers[j] + numbers[i] > target) j -- ;
            if (numbers[j] + numbers[i] == target)
            {
                vector<int> res;
                res.push_back(i + 1), res.push_back(j + 1);
                return res;
            }
        }
        return {};
    }
};