[数据结构与算法]JZⅡ006. 排序数组中两个数字之和

题目描述：

??给定一个已按照升序排序的整数数组numbers，请你从数组中找出两个数满足相加之和等于目标数target。

??函数应该以长度为2的整数数组的形式返回这两个数的下标值。numbers的下标从0开始计数。

??假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

示例：
??输入：numbers = [1, 2, 4, 6, 10], target = 8
??输出：[1, 3]

思路：
??对于该题来说，比较容易想到的思路就是，先遍历一次数组，依次用数组中的每一个数作为第一个数，然后再遍历一次数组，尝试用数组中剩余的数作为第二个数，如果符合要求则将这两个数的下标进行返回即可。这种方式虽然最终能得到正确答案，但是该方法的时间复杂度是$O(N^2)$。

??在解决该题时我们应该充分利用数组有序的特性，用两个变量left和right先分别索引数组的第一个数和最后一个数，然后循环进行以下操作：

1. 将left和right位置的数据相加得到sum。
2. 如果sum大于target，则让right–，使得sum变小。
3. 如果sum小于target，则让left++，使得sum变大。
4. 如果sum和target相等，则将其保持返回。

最终我们就能够得到两个目标数的下标，而该方法的时间复杂度是$O(N)$。

代码如下：

class Solution {
public:
	vector<int> twoSum(vector<int>& numbers, int target) {
		size_t left = 0;
		size_t right = numbers.size() - 1;
		vector<int> ret;
		while (left < right)
		{
			//将left和right位置的数据相加
			int sum = numbers[left] + numbers[right];
			//1、如果sum小于target，则让left++，使得sum变大
			if (sum < target)
			{
				left++;
			}
			//2、如果sum大于target，则让right--，使得sum变小
			else if (sum > target)
			{
				right--;
			}
			//3、如果sum和target相等，则将其保持返回
			else
			{
				ret.push_back(left);
				ret.push_back(right);
				break;
			}
		}
		return ret;
	}
};