百度笔试题 在一个整数数组中寻找符合A+B=C的组合，使C为最大

题目描述：在一个整数数组中寻找符合A+B=C的组合，使C为最大
 输入、输出范例
输入：{ 1, 4, 2, 3 }
输出：1+3=4
输入：{ 2, 3, 1, 4, 5 }
输出：2+3=5
输入：{ 5, 8, 3, 1, 2, 4, 4 }
输出：4+4=8
思路：1：可以先对数组排序，快排的话时间复杂度为O（nlgn），把排好序的数组从最右端向左开始扫描，判断是否能找到符合条件的A与B，找到就停止扫描输出。否则继续扫描

代码如下：

#include "stdafx.h"
#include "stdlib.h"
#include "string.h"

int cmp(const void *a,const void *b)
{
    if(*(int*)a>*(int*)b)
        return 1;
    else
        return 0;

}
bool judgeSum(int &a,int &b,int *array,int j)
{
    int i=0;
    int t=j-1;
    while(i<t)
    {
        if(array[i]+array[t]>array[j])
        {
            t--;

        }
        else if(array[i]+array[t]<array[j])
        {
            i++;
        }else if(array[i]+array[t]==array[j])
        {
            a=array[i];
            b=array[t];
            return true;

        }


    }
return false;

}
int main(int argc, char* argv[])
{
    int array[6]={1,3,2,4,5,100};
    qsort(array,6,sizeof(int),cmp);
    for(int i=0;i<6;i++)
    {
        printf("%d\n",array[i]);

    }
    int j=6;
    int a,int b;
    while(j)
    {
        if(judgeSum(a,b,array,j))
        {
            printf("%d+%d=%d",a,b,array[j]);
            break;

        }
        j--;


    }


}

以上代码整体复杂度为O（n2）。