面经复盘:三次一面都挂在同一类算法题上
- 轮次
- 一面
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 三数之和:给出一个数组,找出所有和为 0 的三元组。复杂度是多少?如果数组里全是 0 呢?
- 手写快速排序,不许调用库函数。请跑一下
[2,1]。 - 最长无重复字符子串。如果输入是
abcbad,你的结果对吗? - 这三次挂掉的真实原因是什么?有没有共同点?
《参考解析》
三数之和:去重要在指针移动时做,不要靠外部容器兜底。 排序加双指针的主体思路是对的(排序 O(n log n),两层循环 O(n²)),但「每找到一组就塞进 set,最后转列表」的写法在极端输入下代价很高:数组全是 0 时,双指针每一轮都能凑出 (0,0,0),集合会被写入 O(n²) 次相同元组,每次都要构造与哈希。正确做法是在固定第一个数后跳过重复值、在双指针命中后分别跳过左右两侧的重复值:
nums.sort()
res = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
res.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
面试官追问「全是 0 会怎样」,考的正是能不能利用「排序」这个前提做剪枝,而不是靠容器去重。
手写快排:分区写法与递归边界必须成套记忆。 作者用 while i <= j 的分区,结束后 j 停在左半区最后一个位置,因此递归应当是 [left, j] 与 [j+1, right],他却写成了 [left, j-1] 与 [j, right],导致长度 2 的数组无限递归。两个补救动作:先写终止条件(left >= right 直接返回),再在纸上用两个元素、三个元素各跑一遍。随机 pivot 只能降低最坏情况概率,不能修复边界错误。
滑动窗口:左边界只能单调右移,移动位置要按上次出现的位置算。 left = right 的错误在于「一遇到重复就把整个窗口丢掉」,abba 这种输入恰好不暴露(重复字符就在窗口起点附近),abcbad 才露馅。正确写法是 left = max(left, last[ch] + 1),或先判断 last[ch] >= left 再更新。本质是记住窗口的不变量:[left, right] 内始终无重复字符。
三次挂掉的共同点是缺少验证环节。 三个 bug 都能被「一个长度 2 的数组」「一个含重复字符的短串」这类最小用例抓出来。作者后来把写题流程固定成四步:先用一句话说清思路与复杂度;再写代码;写完主动报两个边界用例并人肉执行;最后自查循环不变式(窗口内无重复、左半区不大于 pivot、三元组不重复)。面试官要的从来不是一次写对,而是能不能自己发现自己写错了。
一面算法题的分量。 它通常不决定整场面试的成败,但连续三次挂在同一类问题上,说明刷题只是把答案过了一遍脑子,没有把「边界—验证—不变量」变成习惯。把每道做过的题补一份「边界用例清单」,比再刷五十道新题有效。