数据结构与算法 / 系统课时
用快慢指针维护读写边界
用快慢指针维护读写边界
原地修改数组时,真正困难的不是“移动两个指针”,而是明确谁负责读取、谁负责写入,以及何时允许覆盖。本篇用原地移除元素建立快慢指针的不变量,让你能稳定处理去重、删除与保序覆盖。
学习目标
- 说清读指针与写指针的职责,并写出循环不变量
- 用快慢指针完成原地移除元素,并返回新的有效长度
- 判断何时可以覆盖原数组,以及如何验证结果区间
先固定读写职责
把数组看成“未处理区”和“已整理区”。快指针 read 从左到右读取每个元素;慢指针 write 指向下一个可写位置。只有当前元素应该保留时,才执行写入并推进 write。
关键不变量是:每轮循环开始时,区间 [0, write) 已经是所有已扫描元素中应该保留的部分,并且相对顺序不变。 因为 write 永远不会跑到 read 右侧,所以覆盖不会破坏尚未读取的数据。

用不变量写出原地移除
以“移除所有等于 3 的元素”为例。每个元素只读一次,保留元素最多写一次。
python
def remove_element(nums, target):
write = 0
for read in range(len(nums)):
# 只有需要保留的元素才进入已整理区
if nums[read] != target:
nums[write] = nums[read]
write += 1
return write
nums = [3, 1, 3, 2, 4, 3]
length = remove_element(nums, 3)
print(length)
print(nums[:length])预期输出
text
3
[1, 2, 4]write 最终既表示新数组的有效长度,也表示有效区间的右边界。题目若允许原地修改,通常只需要保证 nums[:write] 正确;write 之后的旧值无需清理。
为什么这种写法稳定
若保留元素时总是按扫描顺序写到 write,元素相对顺序就不会改变,所以它天然适合“稳定删除”“稳定去重”这类要求。复杂度为 ,额外空间为 。
还有一种交换式写法:发现待删除元素时,用数组尾部元素覆盖当前位置并缩短检查范围。它可能减少写入次数,但会打乱顺序,因此不能替代稳定覆盖套路。
把套路迁移到去重
面对“有序数组原地去重”,职责仍然相同:read 负责检查新元素,write 负责维护已确认的不重复前缀。区别只是“是否保留”的条件从“值不等于目标”变成“值不同于最后一个已写入元素”。
写代码前先回答三个问题:有效区间在哪里、当前元素何时被接纳、写指针何时移动。 这三个答案一旦明确,快慢指针就不再是记模板,而是对读写边界的直接编码。
按自己的节奏,确认真正理解。