// test20.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<string.h>
#include<deque>
using namespace std;
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array, int sum) {
if (array.empty()) return{};
auto small = array.begin(); //指向小的指针
auto big = array.end()-1; //指向大的指针
auto curr = big;
vector<vector<int>> vec;
vector<int> result;
while (small<big)
{
while (small < curr)
{
if (*small + *curr == sum) //找到第一组就能确定是乘积最小，所以不用做后续的比较
{
result.push_back(*small);
result.push_back(*curr);
vec.push_back(result);
result.clear();
}
else if (*small + *curr < sum)
{
break;
}
else
{
}
--curr;
}
small++;
curr = big;
}
if (vec.empty()) return{};
auto it = vec.begin();//这里面是多余的
int num1= *(it->begin());
int num2= *(it->begin() + 1);
int mult = num1*num2;
++it;
while (it!=vec.end())
{
if (mult >= (*(it->begin()))*(*(it->begin() + 1)))
{
num1 = *(it->begin());
num2 = *(it->begin() + 1);
}
++it;
}
result.clear();
result.push_back(num1);
result.push_back(num2);
return result;
}
};
int main()
{
Solution so;
vector<int> v = { 1,2,3,4,5,6,7,8,9 };
vector<int> vec = so.FindNumbersWithSum(v,9);
for (auto it = vec.begin();it != vec.end();++it)
{
cout << *it << " ";
}
cout << endl;
return 0;
}