输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
题目介绍
输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
题目分析
这个题目很简单,依次遍历即可,而且需要有条件的提前终止搜索,降低时间复杂度,详细思路请见源代码
源代码
class Solution {
public:vector<int> FindNumbersWithSum(vector<int> array,int sum) {vector<int> res;int a=0,b=0,s=65535;bool flag=false;int num=array.size();for(int i=0;i<num;i++){for(int j=i+1;j<num;j++){if(array[i]+array[j]==sum){flag=true;if(s>array[i]*array[j]){s=array[i]*array[j];a=array[i];b=array[j];break;}}}}if(a<=b&&flag){res.push_back(a);res.push_back(b);}else if(a>b&&flag){res.push_back(b);res.push_back(a);}else{return res;}return res;}
};