参考答案
内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 79 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解
要点:
- 决策树:①数组有序且求配对/边界 → 双指针(对撞);②需原地去重/判环/找中点 → 快慢指针;③求「满足条件的连续子数组/子串」→ 滑动窗口;④需多次区间和或「子数组和等于 K」→ 前缀和(+哈希);⑤子矩阵 → 二维前缀和。
- 单调性是关键:双指针/滑动窗口能降复杂度,前提是「扩张与收缩方向确定、无回头」;若数据无序或无单调(如含负数的和),窗口法可能失效,要改前缀和/哈希。
- 复杂度分析框架:
1. 看每个元素被「指针/窗口」访问次数(双指针/滑动窗口通常 ≤ 2n → O(n));
2. 看预处理(前缀和 O(n));
3. 看辅助结构(哈希 O(1) 读写、有序结构 O(log n));
4. 空间 = 哈希表/前缀和数组大小。
- 面试加分项:先说暴力复杂度,再指出瓶颈,给出优化后复杂度与正确性(不重不漏)论证;并主动提边界与变体(如负数、空输入、K=0)。
- 一句话:先识别「有序/连续子区间/区间求和」三类信号,再选对应武器,最后用「指针各走一遍」判定 O(n)。