剑指Offer——和为S的两个数字

时间:2023-03-10 06:36:05
剑指Offer——和为S的两个数字

题目描述:

输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
输入描述:
对应每个测试案例,输出两个数,小的先输出。

分析:

如果有多对数字的和等于S,输出两个数的乘积最小的。

假设这两个数为a,b(a<b)。

a+b=S,为使a*b最小,那么a,b离得越远越好。

因为数组是递增排序的,设置两个指针,指向一头一尾,往中间夹逼。

如果和的结果大于S,那么右边的指针左移。

如果和的结果小于S,那么左边的指针右移。

代码:

 class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array, int sum) {
vector<int> res;
int aSize = array.size();
if(aSize < ) return res;
int left = ;
int right = aSize - ;
while(left < right) {
if(array[left] + array[right] == sum) {
res.push_back(array[left]);
res.push_back(array[right]);
break;
} else if(array[left] + array[right] < sum) {
left++;
} else right--;
}
return res;
}
};