首页 / 面试 / 教你学习大厂面试算法真题解析入门到进阶
教你学习大厂面试算法真题解析入门到进阶
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了教你学习大厂面试算法真题解析入门到进阶，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5279字，纯文字阅读大概需要8分钟。
内容图文
附Java/C/C++/机器学习/算法与数据结构/前端/安卓/Python/程序员必读书籍书单大全：
书单导航页（点击右侧 极客侠栈 即可打开个人博客）：极客侠栈
①【Java】学习之路吐血整理技术书从入门到进阶最全50+本（珍藏版)
②【算法数据结构+acm】从入门到进阶吐血整理书单50+本（珍藏版)
③【数据库】从入门到进阶必读18本技术书籍网盘吐血整理网盘(珍藏版)
④【Web前端】从HTML到JS到AJAX到HTTP从框架到全栈帮你走更少弯路(珍藏版)
⑤【python】书最全已整理好（从入门到进阶）(珍藏版)
⑥【机器学习】+python整理技术书（从入门到进阶已经整理好）（珍藏版）
⑦【C语言】推荐书籍从入门到进阶带你走上大牛之路（珍藏版）
⑧【安卓】入门到进阶推荐书籍整理pdf书单整理（珍藏版）
⑨【架构师】之路史诗级必读书单吐血整理四个维度系列80+本书(珍藏版)
⑩【C++】吐血整理推荐书单从入门到进阶成神之路100+本(珍藏)
?【ios】IOS书单从入门到进阶吐血整理(珍藏版)
-------------------------------------------------------------------------------------------------------------------------------------------
如今想要收获大厂offer，在面试的前几轮，总是躲不开算法这座大山。
常听人说，算法很难。这话没错。算法本身是是一个艰深的方向。但是算法题却有据可循。通过有针对性的学习和练习，我们完全可以掌握解题的基本方法和技巧，见题拆题，扫清通往offer之路上的障碍。
看看手上这些各个大厂的面试算法真题，我想，不如开始一个新的系列，和大家一起解析真题，学习解题方法，开阔解题思路。头脑越练习，越灵光。
接下来，就让我们来看第一题：
题目
[来自Google]
Given a list of numbers and a number k, return whether any two numbers from the list add up to k
给定一组数字，以及一个数字k，确定这组数字中，是否存在任意两个数字，其相加之和等于k。
解析
初次见到一个问题，如果暂时没有什么特别清晰的思路或灵感，不妨安下心来，首先想一想这道题目的暴力解法。
简单粗暴的暴力解法不考虑效率和美观，只考虑正确性，所以往往效率较低。但是，通过观察暴力解法中冗余或者重复的部分，我们就可以找到进一步优化的切入点，想出更有效率的算法。
小技巧： 在面试中，如果暂时头脑空白，想不到漂亮的解法，不妨坦率地用简洁的话语先描述一下暴力解法，在这个过程中发现思路，找到优化解法。这个过程，也有助于面试官考察你的整体解题思路，还可能给你加分哟
暴力解法
这道题的暴力解法很简单。
只要将数组中所有数字对求和，然后和给定的数字k相比较，就知道是否有和k相等的值了。
假设数组中有n个数字，将暴力解法写成伪代码pseudo code的话，就是这个样子：
function sumEqualsToK(array, k):
for i=1 to n-1
for j=i+1 to n
if array[i] + array[j] == k
return true
return false
暴力解法使用了两个嵌套在一起的循环，显而易见，它的时间复杂度是O(n^2)。为了降低时间复杂度，我们来分析一下暴力解法中冗余或者重复的部分。
暴力解法试图对数组中 所有 数字对进行求和操作。
这部分操作是否存在冗余的部分呢？
我们能不能减少需要查看的数字对的数量呢？
想要对这一点进行优化，我们就要利用题目中的另一个线索，也就是数字k了。
其实这道题目就是在给元素“配对儿”。
对于数组中的任一数字array[i]，如果希望它和它的“另一半”相加之和等于k，那就意味着它的“另一半”的值必须是k-array[i]。
也就是说，只要数组中也存在一个等于k-array[i]的元素，就可以满足相加等于k这个条件了：
例子：
k = 10
array = [ 4, 2, 5, 6, 8 ]
那么我们寻找的“另一半”们就是：[ 10-4, 10-2, 10-5, 10-6, 10-8 ]
也就是 [6, 8, 5, 4, 2]
这样一来，我们的问题就转换成：
给定数组 array = [ 4, 2, 5, 6, 8 ]，以及数组 target = [ 6, 8, 5, 4, 2 ]，
array[i]和target[i]是不是同时存在于array中
在这个例子中，大家要格外关注5这个元素
5正好是k值的一半，所以array和target都包含了5
只有在原数组中包含了两个5，才能相加等于10
好了，现在我们已经有了进一步优化暴力解法的思路了。
在揭晓优化解法的伪代码之前，请你先开动脑筋，试着自己把代码写出来吧
思考～思考～
优化解法
时间到～下面就是优化算法的伪代码了：
function sumEqualsToK(array, k):
for i=1 to n
if map contains array[i]
return true
else
put k-array[i] into map
return false
在优化算法中，我们使用了一个map来记录我们想要寻找的“另一半”的元素，也就是之前例子里面提到的target
接下来，我们只需要遍历array一次。
如果array[i]已经和map中的元素相符，就说明array[i]和我们之前遍历到的某一个元素恰好是相加为k的“一对儿”，算法直接返回true。
如果不相符，那么我们就把k-array[i]放进map中去，期待接下来遍历到的元素能够和k-array[i]相符。
这个优化算法只需要遍历array一次，所以它的时间复杂度只有O(n)。而我们最多也只会将array中所有元素的“另一半”放进map中去，所以算法的空间复杂度也是O(n)
实现
想出解法只是第一步，为了正确地实现解法，我们还需要考虑实现中的细节。
让我们想一想这个问题的输入和输出：
输出
这个问题的输出很简单，就是一个boolean值，true/false
输入
题目中对于输入的表达较为模糊
没有说明array的长度，也没有说明元素和k的具体类型
格外要注意的是，由于在解题过程中需要进行求和操作，我们要谨慎选择在实现中使用的变量类型。两数之和的范围可能远远大于单一数字的范围，所以根据实现语言的不同，要小心避免求和操作造成溢出
小技巧：在面试中，遇到题目中比较模糊的描述，一定记得要和面试官沟通，以便得到更多信息。至少，要向面试官询问基本的输入输出的细节。这样一来，面试官可以看出你对于问题的思考较为全面和缜密，也是加分项呢
不同公司的面试方法不同，有些会要求候选人写下完整地实现解法，有些只需要候选人写出伪代码就可以了。但是在练习时，我建议大家还是尽量写下具体的实现，至少也要思考一下实现的细节。
在这个系列里，我不会给出具体的实现代码，因为大家掌握的实现语言各不相同。不过，欢迎大家提出实现时遇到的问题，我们可以集思广益，一起解决～
总结
这道题目很精巧。它不涉及任何著名的，大家耳熟能详的算法，但是可以很好地考察候选人对暴力解法进行优化的完整的思考过程，还可以考察候选人对于输入输出的要求所进行的思考。
小而强大～也许这就是Google使用这道题目的原因吧～
恭喜各位成功解决了第一道大厂面试真题～可以好好休息一下了～
内容总结
以上是互联网集市为您收集整理的教你学习大厂面试算法真题解析入门到进阶全部内容，希望文章能够帮你解决教你学习大厂面试算法真题解析入门到进阶所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。