题目要求：
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。
例如输入数组{1,2,4,7,11,15}和数字15.由于4+11=15，因此输出4和11.
参考资料：剑指offer第41题
题目分析：
方法1 穷举法：两个for，时间复杂度O(n^2).
方法2 二分查找法：逐个遍历选一个数，二分查找选另一个数，时间复杂度O(nlogn).
方法3 双向扫描+临时数组法：先用输入数字s依次减去原数组a，组成一个新数组b：14、13、11、8、4、0.然后从数组a左边开始，b右边开始扫描，小的移动，直到两个数相等，则找到。a中位置的数为第一个数，b中数的位置对应的a中位置的数为第二个数.
方法4 hash法：先用数组建立一个hash表。这样，对于一个输入数字，只用遍历一遍数组就可以找到是否有这样的两个数。时间复杂度O(N).空间复杂度O(N).
方法5 双向扫描：从两端扫描，如果a[i]+a[j]>s,则j--，否则i++，如果最终找到a[i]+a[j] = s,则找到。
代码实现：
#include <iostream> using namespace std; typedef struct Pair
{
int i,j;
}Pair; Pair findSum(int *a, int n,int s); int main(void)
{
int a[] = {,,,,,};
int n = sizeof(a)/sizeof(int);
int s = ;
Pair res = findSum(a,n,s);
if(res.i == -)
cout << "not find" << endl;
else
cout << "find it,and the first number is " << res.i << ",the second number is " << res.j <<endl;
return ;
}
//方法5实现
Pair findSum(int *a, int n,int s)
{
//sort(s,s+n); 如果数组非有序的，那就事先排好序 O（N*logN ）
int *begin=a;
int *end=a+n-;
Pair TwoNums;
while(begin<end) // 俩头夹逼，或称两个指针两端扫描法，很经典的方法， O（N ）
{
if(*begin+*end>s)
{
--end;
}
else if (*begin+*end<s)
{
++begin;
}
else
{
TwoNums.i = *begin;
TwoNums.j = *end;
return TwoNums;
}
}
TwoNums.i = -;
TwoNums.j = -;
return TwoNums;
}