在微软做了四年面试官，分享一下刷 leetcode 的正确姿势

[longSwordMan]

在微软作了三四年的面试官，面过几百人，早已经知道现在的小朋友喜欢刷题，自然不会傻到原原本本的去考 leetcode 的原题。所以最好不要通过死记硬背，想要碰到原题来制霸面试。

划重点：编程面试，只有高频知识点，没有所谓的高频题。

众所周知，微软以及诸多其他大厂的面试算法题主要是以 leetcode 为素材的改编，我现在分享一些面试真题以及我自己和同事作为面试官的改编思路，希望可以帮到还在苦战刷题的同学。我会将大部分的 leetcode 原题过一遍，再附上面试真题的改写思路，尽量讲得傻瓜。由于篇幅限制，在这里我只举几个小栗子，更多面试真题和改写大家可以关注我的专栏文章。

我尽量保持每周两更+回复评论，看后续的反馈情况决定是否改变更新频率以及增减分享的内容，每条评论回复都会看，也可以加微信交流：longswordMAN，注明 V2EX 的 id 即可。

————————————————————————————————————————

废话不多说，正题开始：

我们先来看 leetcode 上第 1 号问题：Two Sum：

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

[zhouwei520]

期待专栏文章

[also24]

@basefas #11
@eastlhu #16
@zhouwei520 #21

翻了下知乎，翻到了原回答和专栏地址：
https://www.zhihu.com/question/32019460/answer/1268448274
https://zhuanlan.zhihu.com/c_1253290991295655936


BTW：看到原回答下面其实也在讨论二分查找解法实际上是 O(nlogn) 而不是 O(log) 的事儿

[Jooooooooo]

好帖子

[gzfrankie]

@also24 二分那道题是 O(logn)啊，那道题跟哈希是没关系的。

这道题暴力解法就是 O(n)，从头到尾扫一次，直到扫到 num[i-1]<num[i] && num[i+1]>num[i+2]成立，那么 num[i]就是拐点。所以如果你提供一个比 O(n)还要慢的方法，不是自作多情么…

二分怎么做？起始范围选[0..n-1]，i 定为中点(n-1)/2

三个条件：
1.若 num[i-1]<num[i] && num[i+1]>num[i+2]成立，那么 num[i]就是拐点
2.若 num[i-1]<num[i] && num[i+1]<num[i+2]，那么前半边的数可以舍弃，二分范围定为[(n-1)/2, n-1]，继续二分
3.若 num[i-1]>num[i] && num[i+1]>num[i+2]，那么后半边的数可以舍弃，二分范围定为[0, (n-1)/2]，继续二分

因为每次二分都可以舍弃一半的数不用看，所以是 logn 。

*以上伪代码简洁起见我没有考虑各种边界条件。

[longSwordMan]

@also24 感谢搬运，给定有序数组，查找目标的情况下二分查找是 O(logn)，如果超过 O （ n ）没理由不用哈希

[longSwordMan]

@gzfrankie 正解

[longSwordMan]

晚些会拉群，加我的人太多操作不过来

[longSwordMan]

@gzfrankie 征用一下哈，很多跟我帖的同学还是不懂

[gzfrankie]

@longSwordMan 没问题的

[angcz]

很棒啊 不过在论坛连载还是有很多不便之处 最好开个博客吧

[also24]

@gzfrankie #24
@longSwordMan #25
我知道为什么会产生误解了，我们说的压根不是同一道题目。

如下图所示，我其实针对的是黄色部分，我所说的题目是：
按照 Two Sum 的题目规则，寻找和为 target 的两个数，但是将给定数组改成有序数组。
针对黄色部分这道题，使用哈希解法和双指针解法的时间复杂度都为 O(n)，二分查找的时间复杂度为 O(nlogn)。


你们在说的是黄色部分的题目，即：
针对 『拐弯数组』，寻找给定的 target 。
针对蓝色部分这道题，使用哈希解法的时间复杂度是 O(n), 二分查找的时间复杂度为 O(logn)

顺带提一句，蓝色部分这道题，其实非常接近 leetcode 上的 『山脉数组中查找目标值』这道题：
https://leetcode-cn.com/problems/find-in-mountain-array/

https://i.loli.net/2020/06/10/tVY6dhJgACaQbsP.png

[also24]

修正 typo -> 你们在说的是蓝色部分的题目

[longSwordMan]

@also24 是啊，所以第一题我没用二分查找啊，用了哈希，这不是整个帖子要表达的么？区别啥时候用哈希啥时候不用

[also24]

@longSwordMan #33
黄色部分是你在 3 楼发的前半部分，被误解成了在第一题的基础上替换为『有序数组』，其它条件不变。

知乎上和你争吵的那位，也是这样理解了，所以才一直认定是 O(nlogn) 的复杂度。

[longSwordMan]

@also24 是的，我其实已经在说第二题了，估计没转过来。。

[also24]

@longSwordMan #35
因为你后面在说 『改编思路』嘛，而且改编 1 、改编 3 都是确实和原题主体内容一致的。
自然会觉得是改编 2 也是从原题上发展而来的。

结果蓝色部分的改编 2，从题目内容角度来说，其实和 Two Sum 已经完全无关了。

[longSwordMan]

@also24 是的，第一篇的改编不是太好，主要是希望从简单题入手。后续可以关注我该系列的第二，第三篇

[also24]

@longSwordMan #37
嗯，搞清楚问题是怎么出现的就好，这样才更有意义~
还是要感谢分享~~

[chendeshen]

这个适合开个微信群

[longSwordMan]

@also24 是的，感谢指出缺点