作者：July，yansha。
致谢：微软100题实现组，狂想曲创作组。
微博：http://weibo.com/julyweibo 。
出处：http://blog.csdn.net/v_JULY_v 。
wiki：http://tctop.wikispaces.com/。
------------------------------
前奏
本章依然同第四章一样，选取比较简单的面试题，同时，恭祝各位旅途愉快。
第一节、寻找满足条件的两个数
第14题（数组）：
题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
分析：首先题目中数组已经是升序了，难度下降了不少，具体的思路有以下几种：
1、直接穷举，从数组中任意选取两个数，判定它们的和是否为输入的那个数字。此举复杂度为O（N^2）。很显然，我们要寻找效率更高的解法。
2、题目相当于，对每个a[i]，然后查找判断sum-a[i]是否也在原始序列中，每一次要查找的时间都要花费为O（N），这样下来，最终找到两个数还是需要O（N^2）的复杂度。那如何提高查找判断的速度列?对了，二分查找。将原来O（N）的时间提高到O（logN），这样对于N个a[i]，都要花logN的时间去查找相对应的sum-a[i]是否在原始序列中，总的时间复杂度已降为O（N*logN）。
3、有没有更好的办法列?咱们可以依据上述思路2的思想，a[i]在序列中，如果a[i]+a[k]=sum的话，那么sum-a[i]（a[k]）也必然在序列中，，举个例子，如下：
原始序列：1、 2、 4、 7、11、15
用输入数字15减一下各个数，得到对应的序列为：
对应序列：14、13、11、8、4、 0
第一个数组向右扫描，第二个数组向左扫描，如果下面出现了和上面一样的数，稍加判断，就能找出这俩个数来了。如上，第二个序列出现了11,4，所以符合条件的两个数，即为4+11=15。怎么样，两端同时查找，时间复杂度瞬间缩短到了O（N）。
4、当然，你还可以构造hash表，正如编程之美第177页所述，给定一个数字，根据hash映射查找另一个数字是否也在数组中，只需用O（1）的时间，这样的话，总体的算法通上述思路3一样，也能降到O（N），但有个缺陷，就是构造hash额外增加了O（N）的空间。不过，空间换时间，仍不失为在时间要求较严格的情况下的一种好办法。
5、最最常见的办法是往往最有效的办法，我们上面都忽略了这种办法，既然数组是有序的，那么可以用两个指针i，j，各自指向数组的首尾两端，令i=0，j=n-1，然后i++，j--，逐次判断a[i]+a[j]?=sum，如果某一刻a[i]+a[j]>sum，则要想办法让sum的值减小，所以此刻i不动，j--，如果某一刻a[i]+a[j]<sum，则要想办法让sum的值增大，所以此刻i++，j不动。时间复杂度也达到了如上述思路2所述的O（N）的复杂度。
6、咱们是不是遇到的都太顺利了，当然，题目完全可以这么变换的，如果数组是非有序的列，我想根据上面所述的各种思路，你也定能很快的想到先排序（N*logN），再查找判断O（N），总起来最佳的时间复杂度为O（N*logN）+O（N）。
7、但有的时候，生活并没有我们想象中的那么美好，如果题目并没有指定是要你找出两个数列?而是从这些数中找出两个，或多个，只要这些数加起来的和为输入的sum就行列?ok，这个问题就是下面第二节将要阐述的背包问题了。
在进入第二节之前，咱们先来实现思路5（这里假定数组已经是有序的），代码可以如下编写：
//O（N）
Pair findSum(int *s,int n,int x)
{
//sort(s,s+n); 如果数组非有序的，那就事先排好序O（N*logN）
int *begin=s;
int *end=s+n-1;
while(begin<end) //俩头夹逼，很经典的方法,O（N）
{
if(*begin+*end>x)
{
--end;
}
else if(*begin+*end<x)
{
++begin;
}
else
{
return Pair(*begin,*end);
}
}
return Pair(-1,-1);
}
扩展：
1、如果在返回找到的两个数的同时，还要求你返回这两个数的位置列?
1、如果把题目中的要你寻找的两个数改为“多个数”，或任意个数列?（请看下面第二节）
第二节、寻找满足条件的多个数
第21题（数组）
2010年中兴面试题
编程求解：
输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.
最新评论