sum 2
描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
对应每个测试案例，输出两个数，小的先输出。
coding horror
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> ret;
if(array.size()==0){
return ret;
};
vector<int> first_nums;
vector<int> second_nums;
int first_index = 0;
int second_index = array.size() - 1;
while(first_index < second_index){ // index越界
int first = array[first_index];
int second = array[second_index];
if( first + second == sum) {
first_nums.push_back(first);
second_nums.push_back(second);
first_index++;
second_index--;
}
else if(first + second < sum){
first_index++;
}
else{ // first + second > sum
second_index--;
}
}
int min_index = 0;
int min; // 未初始化最小值
for(int i =0 ;i < first_nums.size(); i++){
if(first_nums[i]*second_nums[i] < min){
min_index = i;
min = first_nums[i]*second_nums[i];
}
}
ret.push_back(first_nums[min_index]);
ret.push_back(second_nums[min_index]);
return ret;
}
};
maybe ok
#include "stdio.h"
#include <vector>
using std::vector;
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> ret;
if(array.size()==0){
return ret;
};
vector<int> first_nums;
vector<int> second_nums;
int first_index = 0;
int second_index = array.size() - 1;
while((first_index < second_index)&&(first_index <array.size()-1)&&(second_index>0)){// 注意索引不要越界。
int first = array[first_index];
int second = array[second_index];
if( first + second == sum) {
first_nums.push_back(first);
second_nums.push_back(second);
first_index++;
second_index--;
}
else if(first + second < sum){
first_index++;
}
else{ // first + second > sum
second_index--;
}
}
if(first_nums.size()>0){
int min_index = 0;
int min = first_nums[0]*second_nums[0];// 1.如果vector为空可能造成越界，需先判断vector是否为空。2. 用于比较的最小值要先赋初始值。
for(int i =0 ;i < first_nums.size(); i++){
if(first_nums[i]*second_nums[i] < min){
min_index = i;
min = first_nums[i]*second_nums[i];
}
}
ret.push_back(first_nums[min_index]);
ret.push_back(second_nums[min_index]);
}
return ret;
}
};
int main(int argc, char const *argv[])
{
/* code */
int nums[] = {1,1,1,3,1};
std::vector<int> vnums(nums,nums+5);
Solution sol;
std::vector<int> vret;
vret = sol.FindNumbersWithSum(vnums,5);
for(std::vector<int>::iterator it= vret.begin(); it != vret.end();it++){
printf("%d\n", *it);
}
return 0;
}