V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
longSwordMan
V2EX  ›  LeetCode

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

  •  
  •   longSwordMan · 2020-06-10 12:26:10 +08:00 · 9560 次点击
    这是一个创建于 1664 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在微软作了三四年的面试官,面过几百人,早已经知道现在的小朋友喜欢刷题,自然不会傻到原原本本的去考 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]

    77 条回复    2020-11-03 12:28:27 +08:00
    longSwordMan
        1
    longSwordMan  
    OP
       2020-06-10 12:27:45 +08:00   ❤️ 1
    分析:简单题,考的是哈希表,暴力两重循环必挂。现在网上的帖子都喜欢和你说 leetcode 第 XX 题 是高频题,其实都是懒人思维,属于新手的思维误区。真正高频的是一些特定的知识点,如果按这种“原题照搬”思维,题目稍微做一些变招,大概率是要马失前蹄。

    这里的真正的高频考点是数据结构哈希表,划重点:哈希表的应用面试必考,一定会以某种形式在题目的某一部出现,以后还会讲到哈希表和二叉树,哈希表和二位数组等其他数据结构结合的变招。
    longSwordMan
        2
    longSwordMan  
    OP
       2020-06-10 12:28:03 +08:00
    面试官改编思路:
    1. 不同的运算规则,可以是乘除法,可以发明一个运算规则。
    真题:
    给定一个整数数组和一个目标值,找出数组中乘积为目标值的两个数。

    示例:

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

    因为 nums[0] * nums[1] = 2 * 7 = 14
    所以返回 [0, 1]

    其实换汤不换药,乘除法注意考虑边界情况即可(除以零),如果面试官自己发明的运算法:比如运算符:bla 的规则是: X 'bla' Y = X*Y - X -Y 。 同样的,查表规则改一下而已,换汤不换药,注意考虑边界情况 。
    longSwordMan
        3
    longSwordMan  
    OP
       2020-06-10 12:28:16 +08:00
    2. 换一个数据结构,看面试者是否能够利用规则,在时间复杂度上进一步优化。

    当然有序数组也可以改成二叉树等其他数据结构,或者是一些具备某特性的数据结构。有序数组的话,注意用二分查找,可以把时间复杂度降到 O ( logn ),注意哈希表的构建时间复杂度是 O ( n ),能直接用二分查找就直接用,不要考虑哈希。

    真题:

    给定一个“拐弯数组”,由两个有序数组拼接而成,但两数组升降序相反。 如:[1,2,3] + [6, 5, 4] ---> [1,2,3, 6, 5,4]。 要求在拐弯数组中找到给定的 target 。

    这题如果用哈希,虽然是 O(n),但不是最优,没有用到数组的特性。我们先用二分法找到拐点,再到两个有序数组中二分,把复杂度优化到 O ( logn )
    longSwordMan
        4
    longSwordMan  
    OP
       2020-06-10 12:28:28 +08:00
    3. 变成多数之和,比如 3 sum 。这样的改写容易真题:
    给定一个有序整数数组和一个目标值,找出数组和为目标值的三个数。

    示例:

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

    因为 nums[0] + nums[1] + nums[2] = 2 + 7 + 11 = 20
    所以返回 [0, 1, 2]
    longSwordMan
        5
    longSwordMan  
    OP
       2020-06-10 12:28:46 +08:00
    思路类似,查两次表,但注意排除第一个数,比如 2+2+2 这种一个数重复用多次的情况。

    当然这都是容易的,如果三个数,再结合第 1 条变化,查表次数仍然是两次,但不要被复杂的运算搞晕,然后注意边界条件即可。

    看完了这几个我出的改编面试真题,不知道看官们是否对原来的刷题方式有所改观呢?总之,没有所谓的高频题,只有高频知识点,我们刷题的同时也要勤加思考,思考背后的考察知识点,甚至可以依照我上面分享的改编思路,自己给自己出题,这样才能把刷题的效率最大化。刚才说的三类变体,本质上都是对 [哈希表] 这个知识点的考察,如果对题目本身死记硬背,而忽视知识本身,是非常低效的。那么哈希表这个数据结构的意义就在于:可以通过 O ( 1 )的时间复杂度来查找元素是否存在于集合中,而不用 O ( n )来遍历查找。

    下次更新一些新的真题,着重说一些其他的哈希表的面试变招,会结合 leetcode 原题来说。
    noreplay
        6
    noreplay  
       2020-06-10 12:30:35 +08:00 via Android
    等更新,收藏了
    GromHellscream
        7
    GromHellscream  
       2020-06-10 12:35:07 +08:00
    谢谢分享,先收藏一波。
    hdbzsgm
        8
    hdbzsgm  
       2020-06-10 12:38:04 +08:00   ❤️ 1
    是这个思路 我刷题喜欢 按模块来 链表 数组 哈希 树 图 然后再看看 字符串 greedy dp dfs bfs 类似变种的题就差不多了
    longSwordMan
        9
    longSwordMan  
    OP
       2020-06-10 12:44:46 +08:00
    @hdbzsgm 同路中人
    longSwordMan
        10
    longSwordMan  
    OP
       2020-06-10 12:44:58 +08:00
    @hdbzsgm 握爪
    basefas
        11
    basefas  
       2020-06-10 13:11:17 +08:00
    所以说专栏呢?
    also24
        12
    also24  
       2020-06-10 13:19:12 +08:00
    @longSwordMan #3
    有序数组的话,可以直接双指针 O(n) 解决吧

    [ 1, 2, 3, 5, 8, 9 ], target = 8

    1+9 = 10 > 8
    1+8 = 9 > 8
    1+5 = 6 < 8
    2+5 = 7 < 8
    3+5 = 8
    27
        13
    27  
       2020-06-10 13:21:31 +08:00
    @also24 可以,但是也不如二分的 O(logn)快
    also24
        14
    also24  
       2020-06-10 13:23:19 +08:00
    @longSwordMan #3
    对于有序数组二分查找的方案,
    因为第一个数字还是要遍历的也就是 O(n) ,
    然后查询第二个数字的时候走二分查找需要 O(logn),
    所以实际上总体复杂度是 O(nlogn) 吧
    also24
        15
    also24  
       2020-06-10 13:23:50 +08:00
    @27 #13
    二分查找也需要遍历第一个数字的吧,还有个 O(n) 在外面哇
    eastlhu
        16
    eastlhu  
       2020-06-10 13:27:14 +08:00
    期待大佬的专栏
    WhyLevi
        17
    WhyLevi  
       2020-06-10 14:47:39 +08:00 via iPhone
    干货拉满
    xuzywozz
        18
    xuzywozz  
       2020-06-10 15:24:18 +08:00
    多谢分享,收藏了
    yamasa
        19
    yamasa  
       2020-06-10 15:42:20 +08:00
    马克
    yamasa
        20
    yamasa  
       2020-06-10 15:42:31 +08:00
    收藏,后面学习
    zhouwei520
        21
    zhouwei520  
       2020-06-10 15:44:28 +08:00
    期待专栏文章
    also24
        22
    also24  
       2020-06-10 16:01:07 +08:00   ❤️ 3
    @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
        23
    Jooooooooo  
       2020-06-10 17:49:08 +08:00
    好帖子
    gzfrankie
        24
    gzfrankie  
       2020-06-10 18:43:08 +08:00 via iPhone
    @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
        25
    longSwordMan  
    OP
       2020-06-10 18:55:58 +08:00
    @also24 感谢搬运,给定有序数组,查找目标的情况下二分查找是 O(logn),如果超过 O ( n )没理由不用哈希
    longSwordMan
        26
    longSwordMan  
    OP
       2020-06-10 18:56:23 +08:00
    @gzfrankie 正解
    longSwordMan
        27
    longSwordMan  
    OP
       2020-06-10 18:57:14 +08:00
    晚些会拉群,加我的人太多操作不过来
    longSwordMan
        28
    longSwordMan  
    OP
       2020-06-10 20:45:48 +08:00
    @gzfrankie 征用一下哈,很多跟我帖的同学还是不懂
    gzfrankie
        29
    gzfrankie  
       2020-06-10 21:13:45 +08:00 via iPhone
    @longSwordMan 没问题的
    angcz
        30
    angcz  
       2020-06-10 21:52:59 +08:00
    很棒啊 不过在论坛连载还是有很多不便之处 最好开个博客吧
    also24
        31
    also24  
       2020-06-10 22:33:56 +08:00
    @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
        32
    also24  
       2020-06-10 22:36:41 +08:00
    修正 typo -> 你们在说的是蓝色部分的题目
    longSwordMan
        33
    longSwordMan  
    OP
       2020-06-10 22:48:33 +08:00
    @also24 是啊,所以第一题我没用二分查找啊,用了哈希,这不是整个帖子要表达的么?区别啥时候用哈希啥时候不用
    also24
        34
    also24  
       2020-06-10 22:51:35 +08:00
    @longSwordMan #33
    黄色部分是你在 3 楼发的前半部分,被误解成了在第一题的基础上替换为『有序数组』,其它条件不变。

    知乎上和你争吵的那位,也是这样理解了,所以才一直认定是 O(nlogn) 的复杂度。
    longSwordMan
        35
    longSwordMan  
    OP
       2020-06-10 22:54:48 +08:00
    @also24 是的,我其实已经在说第二题了,估计没转过来。。
    also24
        36
    also24  
       2020-06-10 22:57:12 +08:00
    @longSwordMan #35
    因为你后面在说 『改编思路』嘛,而且改编 1 、改编 3 都是确实和原题主体内容一致的。
    自然会觉得是改编 2 也是从原题上发展而来的。

    结果蓝色部分的改编 2,从题目内容角度来说,其实和 Two Sum 已经完全无关了。
    longSwordMan
        37
    longSwordMan  
    OP
       2020-06-10 22:58:56 +08:00
    @also24 是的,第一篇的改编不是太好,主要是希望从简单题入手。后续可以关注我该系列的第二,第三篇
    also24
        38
    also24  
       2020-06-10 23:00:33 +08:00   ❤️ 1
    @longSwordMan #37
    嗯,搞清楚问题是怎么出现的就好,这样才更有意义~
    还是要感谢分享~~
    chendeshen
        39
    chendeshen  
       2020-06-10 23:08:29 +08:00 via Android
    这个适合开个微信群
    longSwordMan
        40
    longSwordMan  
    OP
       2020-06-10 23:12:13 +08:00
    @also24 是的,感谢指出缺点
    ccvzz
        41
    ccvzz  
       2020-06-10 23:14:30 +08:00 via Android
    在地上也看到 lz 了,lz 为啥后来被禁言了[好奇]
    longSwordMan
        42
    longSwordMan  
    OP
       2020-06-10 23:41:40 +08:00
    @ccvzz 我也想知道。。。
    shiji
        43
    shiji  
       2020-06-10 23:43:57 +08:00 via iPhone
    为什么我最近总看到这篇文章...
    Ahian
        44
    Ahian  
       2020-06-11 00:53:08 +08:00 via Android
    权威
    longSwordMan
        45
    longSwordMan  
    OP
       2020-06-11 11:37:05 +08:00
    @Ahian 过奖哈
    longSwordMan
        46
    longSwordMan  
    OP
       2020-06-13 15:41:03 +08:00
    我们接着再看一题,看一看怎么去用动态规划的思路来解题。

    给定整数数列 nums, 找到连续和最大的子数列,并返回数列和和,例:

    Input: [-2,1,-3,4,-1,2,1,-5,4],
    Output: 6

    其中[4,-1,2,1]加起来为 6 。
    longSwordMan
        47
    longSwordMan  
    OP
       2020-06-13 15:41:14 +08:00
    还是老套路,一个角标变两个角标而已,和上题一样,暴力两重循环必挂。那么正确的解法是怎样的呢?我们接下来说这道题背后考察的要点和面试官改编的思路。

    我估计不少人需要 O(n^3)才做得出来,如果我告诉你,这题的最优解法是 O(n),咋一看是不是不敢相信?我们要想不去暴力解,必须要头脑冷静分析,这个子数列的一些特征。作为面试官,如果这题面试者不假思索地写答案,如果还写对了,十有八九是背答案,依然是不给过。
    longSwordMan
        48
    longSwordMan  
    OP
       2020-06-17 12:04:11 +08:00
    如果,我们确定了数组中的某一个元素作为子数列的元素,那么我们该如何找最大的子数列?我们不妨把问题简化一下:如果,我们确定了数组中的某一个元素作为子数列的最末位数,那么我们该如何找最大的子数列?
    longSwordMan
        49
    longSwordMan  
    OP
       2020-06-17 12:14:42 +08:00
    大家可以思考一下,这题的思路在哪,晚上来更新答案。
    longSwordMan
        50
    longSwordMan  
    OP
       2020-06-17 12:25:56 +08:00
    这两天疫情加重,和领导各种开会讨论下一阶段的工作安排,有点忙破头,断了几天大家海涵,接下去会继续我们的问题改写
    longSwordMan
        51
    longSwordMan  
    OP
       2020-06-17 12:28:57 +08:00
    有思路的同学可以回复一下代码实现,晚上我会统一回复
    longSwordMan
        52
    longSwordMan  
    OP
       2020-06-17 22:41:03 +08:00
    我们接着今天早上的话题继续聊。

    今天早上我们谈到当确定了数组中的某一个元素作为子数列的元素,我们该如何找最大的子数列的问题。那我们不妨把问题简化一下:如果,我们确定了数组中的某一个元素作为子数列的最末位数,那么我们该如何找最大的子数列?

    这时候,我们往前看一位,如果以 A[i-1]作为尾数的子数列,加起来全是负值,那么这个以 A[i]为尾数的最大子数列就是{A[i]},只有自身一个元素;反之,如果和是正数,则是 A[i-1]为尾数的子数列,拼上 A[i]。那么以此类推,在一轮循环中,我们找到以 A[i]为终点的子数列最大和,一轮循环过后,就得到我们的答案了。
    longSwordMan
        53
    longSwordMan  
    OP
       2020-06-17 22:41:28 +08:00
    我们举例说明:[−1, 1, −3, 4, −1, 2, 1, −5, 8],以第一个数为终点,最大的子数列就是自己,最大和为-1,第二个数,因为 arr[1]的前一个数 arr[0]为终点的子数列是负数,所以以 arr[1]为终点,最大子数列就是自己,和就是 1,以此类推,直到最后一位。
    longSwordMan
        54
    longSwordMan  
    OP
       2020-06-17 22:41:45 +08:00
    在这里,前一位和后一位的联系就是上述的规则:如果以 A[i-1]作为尾数的子数列,加起来全是负值,那么这个最大子数列就是{A[i]},只有一个元素,反之,则是 A[i-1]为尾数的子数列,拼上 A[i],用前一轮的结果,来推算下一个脚标的结果。
    longSwordMan
        55
    longSwordMan  
    OP
       2020-06-17 22:42:01 +08:00
    代码实现:
    def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A:
    max_ending_here = max(x, max_ending_here + x)
    max_so_far = max(max_so_far, max_ending_here)
    return max_so_far
    longSwordMan
        56
    longSwordMan  
    OP
       2020-06-17 22:42:18 +08:00
    大家可以先思考一下,明天我会继续更新这种题型的变体,如果有疑问可以在评论区留言。
    longSwordMan
        57
    longSwordMan  
    OP
       2020-06-18 11:06:15 +08:00
    在昨天我们讲完了原题,那今天想与大家分享一下这类题型的变体:
    1. 给定一个数列,例如 [−2, 1, −3, 4, −1, 2, 1, −5, 4] , 求一个连续的数列使得数列内的元素乘积最大。
    longSwordMan
        58
    longSwordMan  
    OP
       2020-06-18 11:06:31 +08:00
    第一印象相信大家都会感到,很相似。但我们思考一下终究有什么不同,唯一的不同就是,可能负负得正。那么,我们不仅要记录正向的最大,还要记录负向的最大。方便起见,我们把最大负向值表做最小值。
    longSwordMan
        59
    longSwordMan  
    OP
       2020-06-18 11:36:12 +08:00
    所以,这题动态规划的关系就是:目前角标的最大乘积是,如果该数为负,则和前一位数结尾的最小值相乘,若果为正,则和前一位数结尾的最大值相乘;目前角标的最小乘积是,如果该数为负,则和前一位数结尾的最大值相乘,若果为负,则和前一位数结尾的最小值相乘。
    longSwordMan
        60
    longSwordMan  
    OP
       2020-06-18 11:50:24 +08:00
    我们再看变体 2

    2. 有一个数列,代表牌的顺序,在 21 点游戏中能得到的最高点数(最接近,且小于 21 点)

    参考一下我们前题题的做法,如果向后找爆点了(大于 21 ),则把数组的最左端元素删去,直到小于 21 。由于牌点数大于 21 点的期望是 3 张牌,所以时间复杂度上仍然是 O ( N )
    longSwordMan
        61
    longSwordMan  
    OP
       2020-06-18 11:51:28 +08:00
    也就是著名的二十一点问题,(学会了就可以制霸赌场了)大家思考一下这题作为改编,和原题有什么关联,应该如何去解
    longSwordMan
        62
    longSwordMan  
    OP
       2020-06-18 11:54:02 +08:00
    也就是做四次运算,把最大最小的都考虑上。
    longSwordMan
        63
    longSwordMan  
    OP
       2020-06-19 11:01:06 +08:00
    我们接着通过原题和面试真题改编,看一看关于哈希表的应用。

    我们先来看 leetcode 上第 1 号问题:Two Sum:
    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
    你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

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

    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]
    longSwordMan
        64
    longSwordMan  
    OP
       2020-06-19 11:01:38 +08:00
    简单题,考的是哈希表,暴力两重循环必挂。现在网上的帖子都喜欢和你说 leetcode 第 XX 题 是高频题,其实都是懒人思维,属于新手的思维误区。真正高频的是一些特定的知识点,如果按这种“原题照搬”思维,题目稍微做一些变招,大概率是要马失前蹄。
    longSwordMan
        65
    longSwordMan  
    OP
       2020-06-19 11:02:59 +08:00
    这里的真正的高频考点是数据结构哈希表,划重点:哈希表的应用面试必考,一定会以某种形式在题目的某一部出现,以后还会讲到哈希表和二叉树,哈希表和二位数组等其他数据结构结合的变招。大家可以思考一下在原题基础上我们可以如何改编?下午与大家分享面试官的改编思路。
    longSwordMan
        66
    longSwordMan  
    OP
       2020-06-19 16:50:22 +08:00
    下面给大家分享一下作为面试官的改编思路:
    1. 不同的运算规则,可以是乘除法,可以发明一个运算规则。
    longSwordMan
        67
    longSwordMan  
    OP
       2020-06-19 16:50:40 +08:00
    真题:
    给定一个整数数组和一个目标值,找出数组中乘积为目标值的两个数。
    longSwordMan
        68
    longSwordMan  
    OP
       2020-06-19 16:50:54 +08:00
    示例:
    给定 nums = [2, 7, 11, 15], target = 14
    因为 nums[0] * nums[1] = 2 * 7 = 14
    所以返回 [0, 1]
    longSwordMan
        69
    longSwordMan  
    OP
       2020-06-19 16:51:07 +08:00
    其实换汤不换药,乘除法注意考虑边界情况即可(除以零),如果面试官自己发明的运算法:比如运算符:bla 的规则是: X 'bla' Y = X*Y - X -Y 。 同样的,查表规则改一下而已,换汤不换药,注意考虑边界情况 。
    longSwordMan
        70
    longSwordMan  
    OP
       2020-06-21 13:53:32 +08:00
    接着给大家分享下一个改变思路:
    换一个数据结构,看面试者是否能够利用规则,在时间复杂度上进一步优化。真题:
    给定一个有序整数数组和一个目标值,找出数组中和为目标值的两个数。
    longSwordMan
        71
    longSwordMan  
    OP
       2020-06-21 13:53:44 +08:00
    示例:
    给定 nums = [2, 7, 11, 15], target = 13
    因为 nums[0] + nums[2] = 13
    所以返回 [0, 2]
    longSwordMan
        72
    longSwordMan  
    OP
       2020-06-21 13:53:57 +08:00
    当然有序数组也可以改成二叉树等其他数据结构,或者是一些具备某特性的数据结构。有序数组的话,注意用二分查找,可以把时间复杂度降到 O ( logn )
    longSwordMan
        73
    longSwordMan  
    OP
       2020-06-22 11:06:39 +08:00
    今天继续给大家分享关于这道题的最后一个面试官改变思路:
    变成多数之和,比如 3 sum 。这样的改写容易真题:
    给定一个有序整数数组和一个目标值,找出数组和为目标值的三个数。
    longSwordMan
        74
    longSwordMan  
    OP
       2020-06-22 11:06:53 +08:00
    示例:
    给定 nums = [2, 7, 11, 15], target = 20
    因为 nums[0] + nums[1] + nums[2] = 2 + 7 + 11 = 20
    所以返回 [0, 1, 2]
    longSwordMan
        75
    longSwordMan  
    OP
       2020-06-22 11:07:05 +08:00
    思路类似,查两次表,但注意排除第一个数,比如 2+2+2 这种一个数重复用多次的情况。
    longSwordMan
        76
    longSwordMan  
    OP
       2020-06-22 11:07:14 +08:00
    当然这都是容易的,如果三个数,再结合第 1 条变化,查表次数仍然是两次,但不要被复杂的运算搞晕,然后注意边界条件即可。
    user8341
        77
    user8341  
       2020-11-03 12:28:27 +08:00
    谢谢。变题思路很有意思,学会了就可以自己给自己出题了。 @longSwordMan
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   986 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 21:09 · PVG 05:09 · LAX 13:09 · JFK 16:09
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.