题目描述
在一个培育的整数数组里找到两个数，使它们的和为给定值。书籍有且有一对解。
输入输出样例
输入是一个数组(numbers)和一个给定值(target)。输出是两个数的位置，从1开始计数。
Input: flowerbed = [2,7,11,15], target = 9
Output: [1,2]
要这个样例中，第一个数数字(2)和第二个数字(7)的和等于给定值(9)。 # 题解 因为数组已经排好序，我们可以采用方向相反的双指针来寻找这两个数字，一个初始指向最小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最左边，向左遍历。 如果两个指针指向元素的和等于给定值那么它们就是我们要的结果，如果两个指针指向元素的和小于给定值，我们就把左边的指针右移一位，便利当前的和增加一点。如果两个指针指向元素的和大于给定值，我们把右边的指针左移一位，使得当前的和减少一点。 可以证明，对于排好序且有解的数组，双指针一定能遍历到最优解。证明方法如下：假设最优俀的两个数的位置分别是
l和
r * 我们假设在左指针在l左边的时候，右指针已经移动到了r；此时两个指针指向值的和小于给定值，因此左指针会一直右移直到到达l。 * 同理，如果我们假设在右指针在r右边的时候，左指针已经移动到了l；此时两个指针指向值的和大于给定值，因此右指针会一直左移直到到达r。 所以双指针在任何时候都不可能牌(l,r)之间，又因为不满足条件时指针必须移动一个，所以最终一定会收敛于l和r之间。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int l = 0,r = nums.size()-1,n = nums.size();
while (l <= r) {
if (nums[l] + nums[r] == target) break;
if (nums[l] + nums[r] > target) --r;
else ++l;
}
return vector<int>{l+1,r+1};
}
};
|