双指针
双指针通过两个位置的协调移动减少重复扫描。本文负责有序相向查找、原地压缩和指针距离。
1. 面试核心
先记住这几条，再读正文- 相向双指针。 有序数组可按两端和的大小排除一个端点：和偏小时增大左端，和偏大时减小右端。有序性保证被排除的组合不可能是答案。卡 · 相向移动的排除依据
- 读写指针。 读写指针可保序压缩数组。
read扫描原数组，write表示有效前缀长度，写入始终发生在已读取范围内。卡 · 有序数组去重 - 移动次数。 两个指针各自最多向前 n 次时，总移动量为 O(n)。
2. 相向移动的排除依据
升序数组求两数之和时，和偏小就移动左端。当前左值与任何更小右值相加，都达不到目标。和偏大时，对称地排除右端。
static int[] twoSumSorted(int[] a, long target) {
int left = 0, right = a.length - 1;
while (left < right) {
long sum = (long) a[left] + a[right];
if (sum == target) return new int[]{left, right};
if (sum < target) left++;
else right--;
}
return new int[]{-1, -1};
}
[1,2,4,7]、target=9 返回下标 [1,3]。left<right 保证使用两个位置。先转 long 再加，结果覆盖两个 int 的和。时间 O(n)，额外空间 O(1)。
3. 同向指针与快慢指针
读写指针分别管理输入与输出。read 逐项读取，write 指向下一个可写位置。有效结果始终保存在 [0,write)。
快慢指针以不同速度沿链移动。判环与入口推导见链表。
3.1 有序数组去重
static int unique(int[] a) {
int write = 0;
for (int read = 0; read < a.length; read++) {
if (write == 0 || a[read] != a[write - 1]) {
a[write++] = a[read];
}
}
return write;
}
输入 [1,1,2] 返回 2，有效前缀为 [1,2]。尾部内容不属于结果。write 始终不超过 read+1，因此覆盖的是已处理位置。每项只读一次，时间 O(n)，空间 O(1)。
3.2 固定间距
删除链表倒数第 k 项时，可让快指针先走 k 步。两者再同步前进，直到快指针到末端。使用虚拟头可统一删除原头节点的路径。实现需先约定 k 的合法范围和指针初始位置。
4. 使用边界
无序数据缺少按和排除端点的依据。先排序再搜索需 O(n log n)，原下标也需额外保存。
读写压缩要求先读当前值，再覆盖已处理位置。有序去重依赖相同值相邻，无序去重需额外记录已见值。
5 · 面试题卡片
本页题目与参考回答
5.1 相向双指针求两数之和为何依赖有序性？
考察重点：排除候选的大小关系。
相关内容：相向移动的排除依据。
参考回答
有序性保证和偏小时，当前左值与更小右值也无解。
因此可以安全排除左值。无序输入缺少这个保证，应排序并保留下标，或使用哈希表。
5.2 原地去重返回的长度代表什么，为何不会覆盖待处理项？
考察重点：有效前缀与读写位置关系。
相关内容：有序数组去重。
参考回答
返回值是去重后的有效前缀长度，尾部内容可以忽略；write 始终位于已经读取的范围内。
每轮先读取当前项，确定需要保留时才写入并增加 write。这样写入不会覆盖尚未处理的元素。
5.3 如何用固定间距定位链表倒数第 k 项？
考察重点：同步移动与前驱边界。
相关内容：固定间距。
参考回答
让 fast 先从头走 k 步，再让 fast 和 slow 同步前进；fast 为空时，slow 就在倒数第 k 个节点。
两者始终保持 k 步间距，因此 fast 走到链表末尾时即可确定 slow 的位置。k 必须在 1 到链表长度之间；若要删除该节点，还需保留 slow 的前驱。