双指针基础知识速览

双指针基础知识速览

双指针不是固定的一段代码，而是用两个游标维护一个可证明的不变量。写题前先说明游标代表什么、何时移动，以及移动后排除了哪些候选解。

一、面试常考点

模型	指针关系	典型题	关键不变量
对撞指针	一个从左、一个从右	最接近三数之和、回文	指针外侧的候选已被排除
同向指针	读指针不回退，写/匹配指针单调前进	判断子序列、过滤数组	已处理前缀的顺序或合法性不变
两组有序序列	各自指针只向前	分发饼干、合并有序数组	被跳过的元素不可能形成更优匹配
单调边界	从矩阵一角开始排除一行或一列	有序二维矩阵搜索	每次移动都会删除一整条候选边界

二、写题前的四个问题

1. 输入是否有序？若需要排序，是否允许修改原数组？
2. 两个指针分别表示“待处理”还是“已确认”的位置？
3. 当前比较结果能排除哪一侧的候选，为什么？
4. 空输入、重复值、相等边界和没有答案时返回什么？

排序会改变原数组，若调用方还要使用原数据，先复制再排序：

const values = [...nums].sort((a, b) => a - b)

三、复杂度速记

• 一次线性扫描通常是 O(n)；两个都只向前移动的指针仍然是 O(n)，不是 O(n^2)。
• 先排序再扫描通常是 O(n log n)；扫描阶段的 O(n) 不会改变主阶。
• 额外数组、归一化字符串和排序副本要计入空间复杂度。
• 若要重复查询同一个长字符串，预处理索引可能把每次查询从全量扫描降为按匹配字符查找，但预处理本身有成本。

四、专题导航

• 排序双指针：三数之和与顺序匹配
• 字符覆盖：异位词与最小覆盖子串
• 链表加法：进位与方向
• 滑动窗口：最长无重复子串

30 秒口述模板

我先判断题目能否通过排序或单调性排除候选，再定义两个指针的职责和循环不变量。每次移动都要说明排除了什么，最后补上空输入、重复值、是否修改输入以及时间和额外空间复杂度。