一:题目描述
输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
二:解体分析
最简单的方法,两层for循环,但时间复杂度高
可以采用夹逼的方式,利用两个指针分别指向数组的首位,如果两个数的和大于sum,指向尾部的指针--,如过小于sum,指向头部的指针++,直到找到相等或者start==end结束
对于题目中说多对满足的情况,举例发现,最开始满足条件的对,乘积最小,如
1,2,3,4,5,6,7,8,9 找和为9的两个数
数1 数2 乘积
1,8 , 8
2,7, 14
3,6, 18
4,5 , 20
三:代码实现
class Solution { public: vector<int> FindNumbersWithSum(vector<int> array,int sum) { vector<int> result; if(array.size()<=1) return result; if(array.size()>=2 && array[0]>sum) return result; int start=0; int end=array.size()-1; while(start<end){ if(array[start]+array[end]>sum) end--; else if(array[start]+array[end]<sum) start++; else{ result.push_back(array[start]); result.push_back(array[end]); break; } } return result; } };