【100题】第十四题（数组中找两个数使其和等于输入数）

一，题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

二，题目难点在于时间复杂度控制在O(n)

三，方法一

1，分别从数组前，数组后向中间查找。直到前后相遇！！

2，当前得到currentSum>sum说明：大的数太大（数组递增，后面的数太大）。应该将指向最后的标记向前挪动

3，当前得到currentSum<sum说明：大的数太小（数组递增，前面的数太小）。应该将指向最后的标记向后挪动

4，当前得到currentSum=sum说明：找到答案

#include <iostream.h>
bool FindTwoNumbersWithSum(int data[],unsigned int length,int sum, int& num1,int& num2)
{                            //num1，num2采用的是地址，如果方法内改变则改变的是调用实参的值  
    bool found = false;
    if(length < 1)
        return found;
   
    int begin = 0;
    int end = length - 1;
   
    while(end > begin)
    {
        long curSum = data[begin] + data[end];
       
        if(curSum == sum)
        {
            num1 = data[begin];
            num2 = data[end];
            found = true;
            break;
        }
        else if(curSum > sum)
            end--;
        else
            begin++;
    }
    return found;
}
int main()
{
    int x,y;
    int a[6]={1,2,4,7,11,15};
    if(FindTwoNumbersWithSum(a,6,15,x,y) )
    {
        cout<<x<<endl<<y<<endl;
    }
    return 0;
}

方法二：假如

1，数组为：a={1、 2、 4、7、11、15 }

2，输入sum=15

3，用15减去a数组中每一个元素得到

b={14、13、11、8、4、0 }

4，a数组向右扫描

b数组向左扫描

5，如果a出现了和b一样的数，稍加判断，就能找出这俩个数来了。