（剑指Offer）面试题41：和为s的两个数字

题目：

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s，如果有多对数字的和等于s，输出任意一对即可。

思路：

1、枚举

固定一个数字，然后依次判断数组中该数字后面的数字与它的和是不是等于s。

时间复杂度：O(n^2)

2、前后遍历

利用排序数组的规律，定义两个指针，分别指向数组的首尾，如果两个指针所指的数字大于s，则尾指针-1；如果小于s，则首指针+1；如果等于s，则输出。如果两个指针相遇，仍找不到等于s的两个数，则说明数组中不存在和为s的两个数字。

代码：

#include <iostream> using namespace std; bool FindNumbersWithSum(int data[],int length,int sum,int* num1,int* num2){ bool found=false; if(data==NULL || length<=1 || num1==NULL || num2==NULL) return found; int ahead=length-1; int behind=0; long long curSum=0; while(ahead>behind){ curSum=data[ahead]+data[behind]; if(curSum==sum){ *num1=data[ahead]; *num2=data[behind]; found=true; break; } else if(curSum<sum) behind++; else ahead--; } return found; } int main() { int A[]={1,2,4,7,11,15}; int len=sizeof(A)/sizeof(A[0]); int num1=0; int num2=0; int sum=15; cout << FindNumbersWithSum(A,len,sum,&num1,&num2) << endl; cout<< num1 << " " << num2 << endl; return 0; }

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/390da4f7a00f44bea7c2f3d19491311b?rp=2

输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 

输出描述: 对应每个测试案例，输出两个数，小的先输出。

AC代码：

class Solution { public: vector<int> FindNumbersWithSum(vector<int> array,int sum) { vector<int> result; int len=array.size(); if(len<=1) return result; bool found=false; int pHead=0,pTail=len-1; int curSum=0,greatestSum=INT_MAX,multiply=1; int num1=0,num2=0; while(pTail>pHead){ curSum=array[pHead]+array[pTail]; if(curSum==sum){ found=true; multiply=array[pHead]*array[pTail]; if(multiply<greatestSum){ greatestSum=multiply; num1=array[pHead]; num2=array[pTail]; } pHead++; pTail--; } else if(curSum>sum) pTail--; else pHead++; } if(found==false) return result; result.push_back(num1); result.push_back(num2); return result; } };

转载于:https://www.cnblogs.com/AndyJee/p/4682186.html