【答案解析】一个整数数组，元素取值可能是1～N(N是一个较大的正整数)中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。
方法一：蛮力法。这是最简单的方法，枚举出数组中所有可能的数对，看其和是否为N+1，如果是，则输出。但这种方法一般效率不高。
方法二：先对数组进行排序，然后使用二分查找方法，用两个指示器(front和back)分别指向第一个和最后一个元素，然后从两端同时向中间遍历，直到两个指针交叉。
1)如果A[front]+A[back]＞N+1，则 back--。
2)如果A[front]+A[back]=N+1，则计数器加1，back--，同时front++。
3)如果A[front]+A[back]＜N+1，则front++。
重复上述步骤，O(n)时间就可以找到所有数对，因此总体复杂度为O(nlogn)。
程序代码如下：
#include＜stdio.h＞
void FixedSum(int* a,int n,int d)
{
for(int i=0,j=n-1;i＜n&&j＞=0&&i＜j;)
{
if(a[i]+aD]＜d)
++i;
else if(a[i]+a[j]==d)
{
printf("%d,%d/n",a[i],a[j]);
++i;
-j;
}
else
--j;
}
}
int main()
{
int array[]={1,2,3,4,5};
int len=sizeof(array)/sizeof(array[0]);
FixedSum(array,len,6);
return 0;
}
程序输出结果：
1,5
2,4
方法三：用计数排序，将1～N个数放在一块很大的空间里面，比如1放在1号位，N放在n号位置，O(n)的时间复杂度，然后取值，也是O(n)的复杂度。因此，总体复杂度为O(n)。
引申：如果是任意数组而不是本题的有规律数组，如何求解数组对?即给定一个任意整数数组array[n]，寻找数组中和值为SUM的数对。
最容易想到的就是两重循环迭代，对数组中任意两个数进行求和，看其值是否等于SUM。由于需要两重迭代，所以时间复杂度为O(n*n)
例如：
for(int i=0;i＜n;++i)
{
for(int j=i+1;j＜n;++j)
{
…
}
}
上述方法时间复杂度太高，其实可以参照题目的方法二，先将数组排序后(一般最快的排序算法时间复杂度为O(nlogn))，然后设两个指针指向数组两端，判断两个指针对应元素之和是否为SUM，如果等于SUM，则找到了，继续查找；如果小于SUM，那么首指针递增；如果大于SUM，尾指针递减，直到两个指针相遇时，如果还是没有和为SUM的元素对出现，那么返回false。
除了上述方法外，还可以参照上例中的方法三，将数组存储到hash表中，对每个数m，在hash表中寻找SUM-m，此时时间复杂度为O(n)。需要注意的是，如果数组空间很大，超过了内存的容量，那么可以按照hash(max(m,SUM-m))%g，将数据分到g个小的组中，然后对每个小组进行单独处理，此时时间复杂度还是O(n)。
引申：已知大小分别为m、n的两个无序数组A、B和一个数常数c，求满足A[i]+B[j]=c的所有A[i]和B[j]。
方法一：枚举法。该方法是最容易、也是最简单的方法，枚举出数组A和数组B中所有的元素对，判断其和是否为c，如果是，则输出。
方法二：排序+二分查找法。首先对两个数组中较大数组(不妨设为A)排序；然后对于B中每个元素B[i]在A中二分查找c-B[i]，如果找到，直接输出。此方法的时间复杂度为O(mlogm+nlogm)。
方法三：排序+线性扫描法。该方法是方法二的进一步加强，需要对两个数组排序。首先对A和B进行排序；然后用指针P从头扫描A，用指针q从尾扫描B，如果A[p]+B[q]==c，则输出A[p]和B[q]，且p++，q--;如果A[p]+B[q]＞c，则q--;否则p++。时间复杂度为O(mlogm+nlogn)。
算法如下：
void print_pairs_with_sum(int A[],int B[],int m,int n,int sum)
{
sort(A,A+m);
sort(B,B+n);
int p,q;
P=0,q=n-1;
while(p＜m && q＞=0)
{
if(A[p]+B[q]==sum)
{
cout＜＜"("＜＜A[p]＜＜","＜＜B[q]＜＜")"＜＜endl;
p++,q--;
}
else if(A[p]+B[q]＞sum)
{
q--;
}
else
{
p++;
}
}
}
方法四：Hash法。首先将两个数组中较小的数组(不妨设为A)保存到HashTable中；然后对于B中每个元素B[i]，也采用相同的hash算法在HashTable中查找c-B[i]是否存在，如果存在，则输出。时间复杂度为O(m+n)，空间复杂度为O(min{m，n})。
算法如下：
void print_pairs_with_sum2(int A[],int B[],int m,int n,int sum)
{
map＜int,bool＞hash_table;
int *psmaller=A;
int *pbigger=B;
int nsmaller=(m＞=n)?n:m;
int nbigger=(m＞=n)?m:n;
if(m＞n)
{
psmaller=B;
pbigger=A;
}
for(int i=0;i＜nsmaller;i++)
{
hash_table.insert(pair＜int,bool＞(psmaller[i],true));
}
for(int i=0;i＜nbigger;i++)
{
if(hash_table.find(sum-pbigger[i])!=hash_table.end())
{
cout＜＜"("＜＜pbigger[i]＜＜","＜＜surn-pbigger[i]＜＜")"＜＜endl;
}
}
}