频道栏目
IT货架 > > 正文
和为s的两个数字【微软面试100题第十四题】
网友分享于:Jun 12, 2018 11:46:29 PM    来源: IT货架   

题目要求:

  输入一个递增排序的数组和一个数字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,则找到。

代码实现:

 

  


广告服务联系QQ:1134687142 | 网站地图

版权所有: IT货架- 内容来自互联网,仅供用于技术学习,请遵循相关法律法规. 京ICP备11030978号-1