首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

【口试】【扩展】快速寻找满足条件(两个数的和为指定值)的两个数

2012-11-14 
【面试】【扩展】快速寻找满足条件(两个数的和为指定值)的两个数从上篇文章我们可以看出寻找两个数和为指定值

【面试】【扩展】快速寻找满足条件(两个数的和为指定值)的两个数
从上篇文章我们可以看出寻找两个数和为指定值的较好解法是:
先把数组排序,i = 0,j = N-1,这样a[i]+a[j]正好是一个中间数,如果想减小sum的值,就一直缩小j,如果想增加sum的值,就增加i。
设上面的问题算法为getSumNum(int[] a,int sum),arr为数组,sum为和

扩展问题是:如果寻找三个数字或是任意数字呢?

三个数字的想法:
首先还是数组排序,然后从i=0到n-1进行遍历,遍历a[i]时,在剩下getSumNum(arr',sum-a[i])即可。

任意m个数字的想法:
首先数组排序,然后从i=0到n-1个元素遍历,遍历a[i]时,在剩下的n-1个元素中调用getSumNum(a',sum-a[i]),此时为求m-1个元素和为sum-a[i];接下来,同样的方法,从j=0到n-2个元素遍历,遍历a[j]时在arr'上递归调用getSumNum(a'',sum-a[i]-a[j]),此时为求m-2个元素和为sum-a[i]-a[j];依次递归,知道为求2个元素和为sum-?-?-?...时为止。

不论是求3个数字还好是m个数字,总是能比较穷举法少一个数量级n,比先排序然后二分查找求sum-a[i]也要快。

热点排行