快排是手撕第一高频题，因其能一次性暴露分治逻辑、边界处理和递归/迭代熟练度三类问题；TopK本质是partition复用，平均时间复杂度O(n)；滑动窗口与双指针重工程直觉，LRU考结构设计与迭代器细节。
快排、TopK、滑动窗口、LRU、双指针类（如移动零、有序数组平方）是当前 C++ 面试手撕代码的绝对主力，出现频率远高于其他算法。
为什么快排是手撕第一高频题
不是因为它难，而是它能一次性暴露三类问题：分治逻辑是否清晰、边界处理是否鲁棒、递归/迭代写法是否熟练。面试官常要求用 partition 函数封装分区逻辑，再写 quickSort 主体；若写错 left 和 right 的初始值（比如漏掉 right = nums.size() - 1），或递归调用时传入闭区间却用开区间逻辑，就会直接卡住。
- 基准选第一个元素最安全，避免随机数引入额外依赖
- 分区后必须保证
pivot归位，否则递归子区间会漏元素或越界 - 当输入为空或单元素时，
if (left >= right)必须作为递归终止条件，不能只写==
TopK 问题本质是快排的 partition 复用
面试官不会让你重写一遍快排，而是直接问“找第 K 小的数”，考察你能否把 partition 抽出来单独用。关键点在于：每次 partition 后只递归处理包含第 K 位的那个子区间，时间复杂度从 O(n log n) 降到平均 O(n)。
- 注意 K 是从 1 开始计数，而数组下标从 0 开始，调用前要先减 1
-
partition返回的是 pivot 下标，需和k比较大小决定走左还是右——不是比较值，是比下标 - 若用
nth_element，面试官大概率会追问底层是否稳定、是否修改原数组、是否线程安全
滑动窗口和双指针题更考工程直觉
像 minSubArrayLen、moveZeroes、sortedSquares 这类题，不考复杂逻辑，但极容易在边界上翻车。例如 moveZeroes 中，left 指针代表“下一个非零元素该放的位置”，不是已处理长度；sortedSquares 用双指针从两端向中间填结果数组时，必须用 abs() 比较，且填入位置是 res[i] 而非 res[left]。
立即学习“C++免费学习笔记（深入）”；
- 所有滑动窗口题都默认输入为非空 vector，但面试官可能突然给空输入，
nums.empty()要提前判断 - 窗口收缩条件（如
sum >= target）必须用while而非if，否则漏掉多次收缩机会 - 双指针变量名别用
i/j，用left/right或lo/hi更易讲清意图
LRU 缓存考验结构设计能力
这题不是纯算法，而是数据结构组合题：unordered_map + list 是标准解法，但面试中真正卡人的地方是迭代器失效和节点移动细节。比如 get 时把命中节点移到 list 前端，不能先 erase 再 push_front，因为 erase 后迭代器就无效了；正确做法是用 splice 直接迁移节点。
-
list::splice第二个参数必须是本 list 的迭代器，传错容器会崩溃 -
unordered_map的 value 类型要是list<int>::iterator</int>，不是int*——后者无法支持 O(1) 删除 - 容量为 0 时，
put要先清空再插入，否则可能跳过淘汰逻辑
真正拉开差距的，往往不是会不会写快排，而是写完后能不能立刻意识到：pivot 分区时等于号放在哪一侧会影响稳定性，而面试官下一秒就会问“如果要求稳定，你怎么改”。
