我月薪15k,跳槽张口要到25k,我淡定说回去琢琢,结果隔天HR甩来消息:薪资能给到 35k,我却瞬间打了退堂鼓
刚看到个贴子:原作者月薪15k,跳槽面试顺嘴要了25k,本来想回去“琢磨琢磨”,结果第二天HR直接给到35k,反而被吓退了。
怎么说呢,我觉得这事有意思的点不在钱,而在“自我价值感”。
很多人要价时只是试探,真被答应了会慌:我配吗?能干好吗?到时候干不好是不是立刻露馅。其实这就是典型的“能力没升级,价格先飞了”。
我的看法是,敢要高薪可以,但最好心里有数:你能解决什么问题,能扛多大锅。钱不是白给的,高工资=高期望+高风险。别被吓退,也别被数字冲昏头脑,搞清自己能耐,再谈价,底气才硬。
算法题:最接近的三数之和
那天晚上快十一点,我在公司楼下蹲着喝奶茶刷题,隔壁组一个小伙子跑下来吐槽:“哥,三数之和那个题我会了,怎么换个版本就又不会了?最接近的三数之和是啥玩意儿啊?”我当时脑子里就只有一句话:这不就是换皮版 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³) 嘛,小数据也能过啊”。问题就来了,面试官一般不会跟你讲“数据很小”,人家更想听到那个“排序 + 双指针”的故事。
我就边走回办公室边给他讲思路,他一脸“原来可以这样”的表情,你们看一下是不是也有这种感觉。
先把数组排个序。为啥要排序?因为排完序之后,你就能用两个指针从两边往中间靠,这样才能“有方向地逼近 target”,不然你每次只知道大还是小,指针都不知道往哪儿动。
外层用一个下标 i,当成“第一个数”的位置。
剩下两个人,我们用 left 和 right 两个指针,从 i+1 和 最右边 往中间挤。
每次算出
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