【剪枝】个人练习-Leetcode-167. Two Sum II - Input Array Is Sorted
之前写标题都没加关键词，发现检索起来还是不太方便的。因此以后都加上相关算法的关键词方便检索。
题目链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/submissions/
题目大意：给出一个非递减数组numbers[]和一个目标整数target，求两个下标index1, index2 (index1 < index2)使得刚好numbers[index1] + numbers[index2] == target，题目保证这个组合是唯一的。
思路：暴力做肯定会超时，那么想办法缩小index1和index2的范围即可。不妨将两个数组元素称为num1, num2。因为数组是非递减的，所以num1 <= target/2并且num2 >= target/2。
设数组长度为N，那么数组的最大元素和最小元素分别为num[N-1]和num[0]。由题意一定会有num1 + num[N-1] >= target和num2 + numbers[0] <= target，否则答案就不存在了。
由这以上四个条件缩小index1和index2的范围，再进行遍历，遇到正确答案break即可。由于题意中数组下标从1开始，我们最后的两个结果加上1就好。
完整代码
class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int N = numbers.size();int r1 = N-1;while (numbers[r1]*2 > target)r1--; int l1 = 0;while (numbers[l1] + numbers[N-1] < target)l1++;int l2 = 0;while (numbers[l2]*2 < target)l2++;int r2 = N-1;while (numbers[r2] + numbers[0] > target)r2--;int pos1 = -1, pos2 = -1;for (int i = l1; i <= r1; i++) {for (int j = max(l2, i+1); j <= r2; j++) {if (numbers[i] + numbers[j] == target) {pos1 = i, pos2 = j;break;}}if (pos1 != -1 && pos2 != -1)break;}vector<int> ret = {pos1+1, pos2+1};return ret;}
};
