和为S的两个数字
题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，，如果有多对数字的和等于S，输出两个数的乘积最小的。输出描述:对应每个测试案例，输出两个数，小的先输出。
思路：在递增序列中找两个数使得和为S，积最小，那么那么这两个数的差越大，积越小。我定义两个指针一个指在开头，一个指在结尾，用他们的和与S比较，如果大了，尾指针向前移动；如果小了，头指针向后移动；知道找到或者他们相遇就退出，这样的时间复杂度最多是O(n)
#include<stdio.h>#include<vector>using namespace std;class Solution {public:vector<int> FindNumbersWithSum(vector<int> array,int sum) {int len=array.size();vector<int> arr;if(len<=1) return arr;vector<int>::iterator iter1=array.begin();vector<int>::iterator iter2=array.end()-1;while(iter1<iter2){int tmp=*iter1+*iter2;if(tmp==sum){arr.push_back(*iter1);arr.push_back(*iter2);return arr;}if(tmp>sum) iter2–;if(tmp<sum) iter1++;}if(iter1>=iter2) return arr;}};int main(){return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
都在努力为你驱逐烦恼焦躁，
