题目：

对于一个数组，快速找出两个数字，让这两个数字的和等于一个给定的值，默认假设数组中肯定有至少一组符合要求。

数组a[]={5,6,1,4,7,8,9},sum=10.

解法一：

穷举，遍历数组中所有的2个数字，相加之和看是否等于给定的数字，时间复杂度为N（N-1）/2，既O(N^2)，这种方法效率不高。

1 #include "iostream" 2 using namespace std; 3  4 void sum(int *a,int N){ 5     for(int i=0;i

解法二：

求2个数字之和，假定和为sum，对于元素a[i]只需判断数组中是否存在sum-a[i]，无序数组中查找一个数的时间复杂度为O(n),不对数组进行操作的时间复杂度仍为O（n^2）。如果对数组进行排序，然后才去二分查找的方法，查找一个元素的时间复杂度为O(log2n),总时间复杂度为O(n*log2n)。而排序的过程只需要进行一次，时间复杂度为O(N*log2n),所以总时间复杂度仍为O(n*log2n)。

解法三：

换个角度，对于有序序列，从两头分别取数，之和大于sum，j--，之和大于sumi++。将排序号的数组遍历一遍即可输出全部的结果。

1 #include "iostream" 2 #include "algorithm" 3 using namespace std; 4  5 void sum(int *a,int N){ 6 int i,j; 7     for(i = 0,j = N-1;i

 

扩展问题：

1，将两个数字改为3个数字。

假设找到了3个数ai，aj，ak，ai+aj+ak=sum，既ai+aj=sum-ak。i,k从左侧遍历，j从右侧遍历。以sum=17为例，会输出三组满足条件的数。

1 #include "iostream" 2 #include "algorithm" 3 using namespace std; 4  5 void sum(int *a,int N){ 6 int i,j,k; 7 for(k=0;k