引用
【面试】快速寻找满足条件(两个数的和为指定值)的两个数
题目:
能否快速找出一个数组中的两个数字,让这两个数字之和等于一个给定的数字,为了简化起见,我们假设这个数组中肯定存在至少一组符合要求的解。
解法:
思路1:
暴力穷举O(n^2)
思路2:
对数组预排序O(NlogN),然后遍历该数组,对每一个数a,都进行查找Sum-a在不在数组中。这种查找在二分查找下需要O(logN),所以综上效率为O(NlogN)+O(N)*O(logN)=O(NlogN).
思路3:
如果在一定的限制条件下,比如说1,数字均为int型,2,此中int型数的范围有一定限制。则可以考虑用hash来获得O(1)的查找效率。方法,首先遍历一遍数组,初始化hash表O(N),然后再次遍历数组,对每一个数字a进行查找SUm-a只需O(1),所以总的效率为:O(N)+O(N)*O(1)=O(N).
思路4:
首先预排序O(NlogN).然后在一个循环体里使用两个循环变量进行反向遍历,并且这两个变量遍历的方向是不变的,从而保证遍历算法的时间复杂度为O(n)。即令i = 0,j = N-1,这样a[i]+a[j]正好是一个中间数,如果想减小sum的值,就一直缩小j,如果想增加sum的值,就增加i。刚开始一直无法理解这样子一定可以找到这个和么?难道不会漏掉了解得位置。可以这么理解,假如排好序后的数组为1,3,6,a,9,12,17,28,b,35,46 ,那么i最初指向1的位置,j最初指向46的位置,比如所求的是Sum=a+b,a<b,ab在其中数组中某位置上。那么i和j在变化过程中,只考虑i遇到了a或者j遇到了b的时候,必定有一个先遇到,比如i遇到了a,那么这个时候j必定还没指到b,故这是j指到的比b大,从而j减小直到b位置。同理若j先指到了b位置,那么i必定还没指到a(这是我们的前提),然后i现在指到的比a小,故,i增加,直到a位置。
分享到:
相关推荐
python python_leetcode面试题解之寻找两个正序数组的中位数
hadoop2面试题 - 迅速在两个含有大量数据的文件中寻找相同的数据.pdf
java基础面试题和为s的两个数字本资源系百度网盘分享地址
java面试 java面试_leetcode面试java编程题解之第4题寻找两个正序数组的中位数_java题解
给定一个整数数组 nums 和一个整数目标值 target,请您在该数组中找出两个元素的和等于目标值,并返回这两个元素的索引。
两个程序员面试经验和题目两个程序员面试经验和题目两个程序员面试经验和题目!!
一个比较经典的面试题目,从时间复杂度的角度分析了几种解决方案的优劣,值得一看。
很全面的数值后端面试题,总结了很久,希望对你们又帮助。
数字后端笔面试题集锦,共150道左右的题,带书签,涵盖设计流程、文件格式、STA等,对于找数字IC后端的朋友很有帮助
对于任意两个矩形,空间上有包含、相离、相交三种空间关系,现要求设计一个算法判断两个矩形的空间关系,如果两个矩形相交,计算相交部分。 4. 某国土局需要建设一个综合管理信息平台以满足国土资源管理的业务需要...
自己面试的两个SQL,回去自己建表查询出来,感觉不错,共享一下
面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现直接插入排序 面试题2:编码实现希尔(Shell)排序 11.2 交换排序 面试题3:编码实现冒泡排序 面试题4:编码实现快速...
找出两数之和:给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 找出最长子串:给定一个字符串,找出不包含重复字符的最长子串的长度。 判断回文数:判断一个整数是否是回文数。 合并两个有序数组:...
一道华为面试的题目~题目不复杂~123456789×987654321
1.提取出某日访问百度次数最多的那个IP 2.有一个1G大小的一个文件,里面每一行是...5.腾讯面试题:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中? ......
数字IC设计笔试面试经典100题,推荐看,都是常问的一些问题,有参考答案
任意大的两个整数相乘,代码。是一道面试题的答案。
【面试笔试】写两个函数,完成文件分割与合并的功能。假设每个分割文件的大小为100KB,被分割文件的大小不限。分割的第1个文件含有文件合并的信息(以下简称 信息块),即通过解析第1个文件,即可完成文件合并的操作...
两个面试的项目