数据结构与算法 / 系统课时

用快慢指针维护读写边界

用快慢指针维护读写边界

原地修改数组时,真正困难的不是“移动两个指针”,而是明确谁负责读取、谁负责写入,以及何时允许覆盖。本篇用原地移除元素建立快慢指针的不变量,让你能稳定处理去重、删除与保序覆盖。

学习目标

  • 说清读指针与写指针的职责,并写出循环不变量
  • 用快慢指针完成原地移除元素,并返回新的有效长度
  • 判断何时可以覆盖原数组,以及如何验证结果区间

先固定读写职责

把数组看成“未处理区”和“已整理区”。快指针 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,元素相对顺序就不会改变,所以它天然适合“稳定删除”“稳定去重”这类要求。复杂度为 O(n)O(n),额外空间为 O(1)O(1)。

还有一种交换式写法:发现待删除元素时,用数组尾部元素覆盖当前位置并缩短检查范围。它可能减少写入次数,但会打乱顺序,因此不能替代稳定覆盖套路。

把套路迁移到去重

面对“有序数组原地去重”,职责仍然相同:read 负责检查新元素,write 负责维护已确认的不重复前缀。区别只是“是否保留”的条件从“值不等于目标”变成“值不同于最后一个已写入元素”。

写代码前先回答三个问题:有效区间在哪里、当前元素何时被接纳、写指针何时移动。 这三个答案一旦明确,快慢指针就不再是记模板,而是对读写边界的直接编码。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用快慢指针维护读写边界

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通