Python技术迷

我月薪15k,跳槽张口要到25k,我淡定说回去琢琢,结果隔天HR甩来消息:薪资能给到 35k,我却瞬间打了退堂鼓

刚看到个贴子:原作者月薪15k,跳槽面试顺嘴要了25k,本来想回去“琢磨琢磨”,结果第二天HR直接给到35k,反而被吓退了。

Image

怎么说呢,我觉得这事有意思的点不在钱,而在“自我价值感”。

很多人要价时只是试探,真被答应了会慌:我配吗?能干好吗?到时候干不好是不是立刻露馅。其实这就是典型的“能力没升级,价格先飞了”。

我的看法是,敢要高薪可以,但最好心里有数:你能解决什么问题,能扛多大锅。钱不是白给的,高工资=高期望+高风险。别被吓退,也别被数字冲昏头脑,搞清自己能耐,再谈价,底气才硬。

算法题:最接近的三数之和

那天晚上快十一点,我在公司楼下蹲着喝奶茶刷题,隔壁组一个小伙子跑下来吐槽:“哥,三数之和那个题我会了,怎么换个版本就又不会了?最接近的三数之和是啥玩意儿啊?”我当时脑子里就只有一句话:这不就是换皮版 3Sum 嘛。

你先想象一下场景哈:给你一堆整数,随便长这样:

nums = [-1, 2, 1, -4]
target = 1

让你从里面挑三个数出来,三个数加起来的和,要尽量靠近 target,比方说上面这个例子,所有三元组的和是:

  • (-1 + 2 + 1) = 2
  • (-1 + 2 + -4) = -3
  • (-1 + 1 + -4) = -4
  • (2 + 1 + -4) = -1

离 1 最近的是 2,所以答案就得返回 2。不是问你“差值”,就是要你“和”,这个很多人一上来就写错。

结果那个小伙子写了个三重 for…我看了一眼,笑出了声,他说“咋了哥,这不就 O(n³) 嘛,小数据也能过啊”。问题就来了,面试官一般不会跟你讲“数据很小”,人家更想听到那个“排序 + 双指针”的故事。

我就边走回办公室边给他讲思路,他一脸“原来可以这样”的表情,你们看一下是不是也有这种感觉。

  1. 先把数组排个序。为啥要排序?因为排完序之后,你就能用两个指针从两边往中间靠,这样才能“有方向地逼近 target”,不然你每次只知道大还是小,指针都不知道往哪儿动。

  2. 外层用一个下标 i,当成“第一个数”的位置。

  3. 剩下两个人,我们用 left 和 right 两个指针,从 i+1 和 最右边 往中间挤。

  4. 每次算出 s = nums[i] + nums[left] + nums[right]:

  • 如果 s 恰好等于 target,那直接收工,这已经是最接近的了。
  • 如果 s 比 target 小,那想让和再大一点,只能左指针往右挪一格。
  • 如果 s 比 target 大,那就让和小一点,右指针往左挪。
  • 全程维护一个“当前最接近的和”,遇到更接近的就更新。

  • 听起来有点抽象对吧,我直接上 Python 代码,你可以一边看一边在纸上演一遍就很清楚了。

    from typing import List

    defthree_sum_closest(nums: List[int], target: int) -> int:
    # 先排个序,方便双指针移动
        nums.sort()
        n = len(nums)
    # 随便先拿前三个当“当前答案”,后面不断改进它
        best = nums[0] + nums[1] + nums[2]

    for i in range(n - 2):
    # 这里可以加点剪枝优化,不过先别急,一步一步来
            left, right = i + 1, n - 1

    while left < right:
                s = nums[i] + nums[left] + nums[right]

    # 如果这次更接近 target,就更新 best
    if abs(s - target) < abs(best - target):
                    best = s

    # 完全命中,直接返回
    if s == target:
    return s
    # 和偏小,想办法变大:左边往右挪
    elif s < target:
                    left += 1
    # 和偏大,想办法变小:右边往左挪
    else:
                    right -= 1

    return best

    这个代码基本就是“面试可直接抄”的版本了,逻辑也比较直白。

    有人会问:为啥 best 一开始随便拿前三个就行,不怕翻车吗? 其实没事,原因很简单:我们后面会遍历所有合法的三元组,每次只要发现有一个和更接近 target,就把 best 改成它,最后留下来的肯定是“全局最接近”。所以初值只要是某个实际存在的三数之和就行。

    再有个小坑,很多人写着写着就开始“去重”了,以为和 3Sum 一样要去掉重复三元组。这个题其实完全不用管,有重复的三元组也没关系,反正你最后只要一个“和”,而且你只关心“差距谁最小”,重复几次也不会影响结果。你真要去重,还得多写一堆 while left < right and nums[left] == nums[left-1]: 之类的,纯属给自己找麻烦。

    顺便算一算复杂度:排序是 O(n log n),外层 i 一层循环 O(n),里边双指针一共扫一遍数组 O(n),合起来大概就是 O(n²)。这个在面试语境里已经是“标准解”了,不会有人让你搞什么 O(n log n) 的黑魔法。

    我当时跟小伙子讲完,他在工位上跑了一下样例,又自己随便造了个:

    print(three_sum_closest([0, 0, 0], 1))      # 0
    print(three_sum_closest([1, 1, 1, 0], -100)) # 2

    看输出觉得挺顺眼,就开始自信心爆棚:“这也没多难嘛”。我说你别飘,这种题真正容易出错的地方反而是细节 —— 比如:

    • 忘了先排序,结果指针乱飞;
    • best 用成了“差值”而不是“和”,最后 return 写错;
    • while 条件写成 left <= right,然后下标越界;
    • target 比所有 possible 和都大/都小的时候,初值选不对就挂了。

    你可以自己试着改一改代码,故意把某一行写错,然后喂一些极端数据进去,比如全是负数、全是正数、数组长度刚好是 3 之类的,看一眼会不会炸,这比光过几个样例靠谱多了。

    行了,差不多就这样,我得去泡杯咖啡了。你要是下次刷到“最接近的 K 个数”之类的题,再想想这个“排完序用双指针往目标逼近”的套路,基本都是一个家族出来的。

    -END-

    我为大家打造了一份RPA教程,完全免费:songshuhezi.com/rpa.html

    🔥虎哥私藏精品🔥

    虎哥作为一名老码农,整理了全网最全《python高级架构师资料合集》,总量高达650GB