2.12 快速寻找满足条件的两个数

题目：能否快速找出一个数组中的两个数字，让两个数字之和等于一个给定的值，为了简单起见，我们可以假设这个数组中肯定存在至少一组符合要求的解。

 

解法1：巧妙转化，然后二分查找。一般情况下，枚举2个未知数的时间复杂度为O(n^2)，我们应该尽可能避免这种情况。枚举一个未知值，然后利用已知的特定条件限制另一个未知值。本题中要求A+B=Y，我们可以枚举A的值，然后在数组中二分查找(Y-A)的值，若成功找到，则为解。时间复杂度为O(nlogn)

 

解法2：先排序，然后设置头尾指针l、r，根据a[l]+a[r]与目标值的大小比较结果，移动指针。

    while(r>l)
    {
        if(a[l]+a[r]>target)
            r--;
        else if(a[l]+a[r]<target)
            l++;
        else
            break;   
    }