167. 两数之和 II - 输入有序数组]
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。示例:
输入: numbers= [2, 7, 11, 15], target=9
输出: [1,2]
解释: 2与7之和等于目标数9。因此index1=1, index2=2。
第一次
vector<int>twoSum(vector<int>&numbers, inttarget) {
vector<int>vIndex;
vIndex.reserve(2);
if (numbers[0] +numbers[1] ==target)
{
vIndex.push_back(1);
vIndex.push_back(2);
returnvIndex;
}
intmax=0,min=0;
for (inti=numbers.size()-1;i>=0;--i)
{
if (numbers[i] >target&&numbers[i-1] <=target)
{
max=i-1;
break;
}
}
while (max>min)
{
intmid= (max+min) /2;
if (numbers[max] +numbers[min] ==target)
{
vIndex.push_back(min+1);
vIndex.push_back(max+1);
returnvIndex;
} elseif (numbers[mid]*2>target){
max=mid;
}
elseif (numbers[mid]*2<target) {
min=mid;
}
}
returnvIndex;
}
输入为[2,3,4] 6
这种情况就是尾数比target还要大，所以有缺陷
还有就是 有序数组的第一个元素可能为 负数 ，比如[-3,1,2,3,4]，target为 0 ，这样的话，第一步会直接定位到 1 这个元素，所以，找max的那里有缺陷
for (inti=numbers.size()-1;i>=0;--i)
{
if (numbers[0]+numbers[i] <=target) { max=i; break; }
elseif (numbers[0] +numbers[i] >target&&numbers[0] +numbers[i-1] <=target)
{
max=i-1;
break;
}
}
加上首元素，numbers[0]+ numbers[i]来判断就可以防止这种情况了。还有就是要判断尾元素是不是就比target小的情况。
第三次：
vector<int>vIndex;
vIndex.reserve(2);
if (numbers[0] +numbers[1] ==target)
{
vIndex.push_back(1);
vIndex.push_back(2);
returnvIndex;
}
intmax=0,min=0;
for (inti=numbers.size()-1;i>=0;--i)
{
if (numbers[0]+numbers[i] <=target) { max=i; break; }
elseif (numbers[0] +numbers[i] >target&&numbers[0] +numbers[i-1] <=target)
{
max=i-1;
break;
}
}
//cout << "max " << max << endl;
while (max>min)
{
intmid= (max+min) /2;
//cout << "max " << max << " min" << min << " mid "<
if (numbers[max] +numbers[min] ==target)
{
//cout << "numbers[max] + numbers[min] == target" << endl;
vIndex.push_back(min+1);
vIndex.push_back(max+1);
returnvIndex;
} elseif (numbers[mid]*2>target){
max=mid;
}
elseif (numbers[mid]*2<=target) {
min=mid;
}
}
returnvIndex;
输入为 [1,2,3,4,4,9,56,90] 8
这种最中间的两个元素是最终结果，所以要在 numbers[mid] *2
第四次：就告诉我超出时间限制了。。
直接双指针，简单粗暴！！
vector<int>twoSum(vector<int>&numbers, inttarget) {
intlow=0, high=numbers.size() -1;
while (low<high) {
intsum=numbers[low] +numbers[high];
if (sum==target)
returnvector<int>{ low+1, high+1 };
elseif (sum<target)
++low;
else
--high;
}
return { -1, -1 };
}
