学步园

问题：给定一个排序数组，在数组中查找两个数，使两个数的和正好为S.

   我们定义两个指针left
和right，一个指向数组第一个元素，一个指向数组的最后一个元素，如果这两个指针指向的元素的和currentSum正好是S，则输出这两个数，如果currentSum>S,则时right向做移动，如果currentSum<S，则使left向右移动，直到找到这两个元素或者left>right终止。

代码如下：

#include<iostream>
using namespace std;
bool Find(int data[],int length,int sum,int&num1,int&num2);

int main()
{
    int data[10];
    for(int i=0;i<10;i++)
        data[i]=(i+1);
    int num1,num2,Sum;
    cout<<"Please Enter The Sum"<<endl;
    cin>>Sum;
    if(Find(data,10,Sum,num1,num2))
        cout<<num1<<"   "<<num2<<endl;
    else
        cout<<"No Such Element"<<endl;
    return 0;
}
bool Find(int data[],int length,int sum,int& num1,int& num2)
{
    if(length<=0||data==NULL)
        return 0;
    bool find = false;
    int left=0;
    int right=length-1;
    while(left<right)
    {
        long long currentSum= data[left]+data[right];

        if(currentSum==sum)
        {
           num1=data[left];
           num2=data[right];
           find = true;
           break;
        }
        else if(currentSum>sum)
            right--;   //右指针向左移动
        else
            left++;   //做指针向有移动
    }
    return find;
}

Reference

《名企面试官精讲典型编程题》 何海涛