本文主要向大家介绍了C++语言之快速寻找满足条件的两个数，通过具体的内容向大家展示，希望对大家学习C++语言有所帮助。

能否快速找出一个数组中的两个数字，让这两个数字之和等于一个给定的数字，为了简化起见，我们假设数数组中肯定存在这样一组以上符合要求。

这个题目看起来其实并不难，但是仔细想想还是有许多值得思考的地方。

方案一：常人常规蛮力法。穷举法，需要找数据我们就挨个找，总是能找出来，就是时间问题，我么一次列举每一个数和后一个数的和看是否与目标值相等。但是其时间复杂度为O(N*N)。

方案二：由于是查找，我们就可以对其进行排序操作，先排序再查找。为什么要排序呢?这里可以将问题转化一下?既然是寻找和为Sum的两个数，那么我们就可以查找Sum-arr[i]是否在数组中，在排序后我们就可以使用我们非常熟练的二分查找算法，这样查找一个数据的时间复杂度就降低到了O(logN)，但是需要对每一个元素都需要查找，所示其实时间复杂度为O(N*logN)。另外对数据进行排序，我们可以知道其时间复杂度为O(N*logN)，综合其时间复杂度为：O(N*logN)。

方案三：时间换空间的方法。我们采用一个hash表将所有的数据映射到表中，然后Sum-arr[i]只需要O(N)的时间久可以了，这样的话，其时间复杂度就被我们降低到了O(N)+O(N)的辅助空间。

方案四：基于求一个整数的所有连续的有序序列的启发，我们可以先对数组进行排序，时间复杂度为O(N*logN)，然后对于给定的Sum，i=0,j=N-1,我们首先看arr[i]+arr[j]是否等于Sum，如果小于则i++;否则j--，这样在O(N)的时间复杂度就可以完成。综合总的时间复杂度为：O(N*logN)。

方案四实现代码：

void Find(int *arr,int *data1,int *data2,int lenght,int Sum)

{

    int i,j;

    for(i=0;j<lenght;i<j)

    {

        if(Sum==arr[i]+arr[j])//找到了；

        {

            *data1=arr[i];//记住这两个数；

            *data2=arr[j];

        }

        else if(arr[i]+arr[j]<Sum)

            i++;

        else

            j--;

    }

}

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！