删元素不是真删：原地改数组时，读指针为什么要跑在写指针前面
原地修改数组常被当成"不申请额外变量"的炫技，它的本质其实是在同一块存储上重新划分"已定稿"与"未读"两个区域，用覆盖代替删除。最常见的误区是以为按下标删除是 O(1)，或者在遍历中直接删元素，结果漏删、越界、破坏相对顺序。理解写指针为什么永远不该越过读指针，就能统一解释去重、移除元素、移动零、旋转与下标标记这几类题，也能解释工程里 remove_if、迭代器失效和切片别名为什么会出问题。本文给出可复用的不变量、写次数取舍与一套自查清单。
是什么
原地修改（in-place）指的是只使用常数个额外变量——几个下标、一个计数、一个临时值——直接在输入数组占用的存储上完成变换，额外空间记为 O(1)，一般不计输入与输出本身。
一句话直觉：数组是一排已经编好号、退不掉租的储物格，所谓"删除"并不是把格子清空，而是把后面要保留的东西往前挪，再用一个长度变量把队尾划到逻辑边界之外。物理上什么都没消失，只是有效区间变短了。
这决定了它的典型场景：去重与移除元素（LeetCode 26）、移动零、整体旋转、按值三路分区，以及值域恰好等于下标的"下标当哈希"；工程里则出现在缓冲区压缩、日志过滤、协议解析时把有效载荷往前搬。它们共享同一个约束：不能新建一个等长数组，只能在原址上把数据重新排布。
核心原理
覆盖为什么不会丢数据，靠的是一条简单的不等式。 设 read 从左到右扫描，write 指向下一个要落笔的位置，两者初值都是 0。只有当前元素需要保留时，才执行 nums[write] = nums[read] 并让 write 加一；而 read 每轮必加一。也就是说，write 的增量永远不超过 read 的增量，初值又相等，所以任意时刻都有 write <= read。
这条不等式就是全部理由：落笔位置要么就是当前读位置（自己写自己），要么是更早被读过、已经被判定为垃圾的格子。区间 [0, write) 是定稿区，[write, read) 是等待被覆盖的垃圾区，[read, n) 是未读区，三段拼起来正好是整个数组。写指针一旦跑到读指针前面，就意味着要覆盖一个还没看过的元素，数据必然丢失。
def compact(nums, val):
write = 0
for read in range(len(nums)):
if nums[read] != val:
nums[write] = nums[read] # 此时必有 write <= read
write += 1
return write # 逻辑长度，物理长度不变
a = [0, 1, 2, 2, 3, 0, 4]
n = compact(a, 2)
assert a[:n] == [0, 1, 3, 0, 4]
assert n == 5这段代码把"删除"拆成了两件事：保留者前移、返回值缩短逻辑长度。被删掉的 2 其实还躺在数组尾部，只是不再属于有效区间——这也是原地题经常要求返回新长度而不是返回数组的原因。
写次数决定了该用快慢还是对撞。 快慢指针的写次数等于保留元素个数，每个保留者至多搬一次，并且天然保序；首尾对撞的写次数等于被删元素个数，每次把尾部一个待留元素换到前面，代价是顺序被打乱。移动零要求非零元素的相对顺序不变，若用对撞交换，[0,1,0,3,12] 会被换成 [12,1,3,0,0] 之类的结果，非零元素的先后关系已经变了。所以动笔前先问一句：顺序要不要保？保序选快慢；删除比例很高且明确不保序，选对撞，写放大能从 O(n) 降到 O(删除数)。
整体旋转可以拆成三次反转。 把数组切成 A|B 两段，整体反转得到 rev(B)|rev(A)，再分别反转这两段，就回到 B|A，正好是右旋 k 位的结果。k 要先对 n 取模，k=0 时其中两段是空操作。三次反转合计约 2n 次元素写入，时间 O(n)、空间 O(1)。它的好处是不依赖额外数组、边界简单；坏处是写次数比环状替换多，而且这套写法依赖随机访问，对链表并不友好。
当下标本身就是哈希表时，可以借用符号位。 若数组长度为 n、元素值恰好落在 1..n，遍历到 v 时把 nums[|v|-1] 取负，就等于标记"这个下标对应的值出现过"；第二遍再看哪些位置仍是正数，下标加一就是缺失值（LeetCode 448）。取负而不是置零，是为了保留原值供后续读取，读的时候必须先取绝对值。限制也很硬：值域必须合法、不能含 0（-0 仍是 0，标记无效）、结束后若要复用数组还得再扫一遍还原，而且它天生不是并发安全的。
三路分区考的是"交换后指针动不动"。 荷兰国旗问题把数组划成四段：[0, low) 是已确认的 0，[low, mid) 是已确认的 1，[mid, high] 是未知区，(high, n) 是已确认的 2。遇到 0 与 low 交换后，low 和 mid 都要前进，因为换进来的是已经检查过的 1；遇到 2 与 high 交换后只让 high 后退、mid 不动，因为从右侧换进来的是尚未检查的元素。这一处"该不该前进"是整段代码唯一容易写错的地方，也是面试官最爱追问的细节。
常见考点与误区
- 误区一："按下标删除是 O(1)"。
del nums[i]、list.pop(i)、ArrayList.remove(i)都要把后面的元素整体前移，单次是 O(n)。在 for 循环里按下标删更糟：删除后后一个元素补到当前下标，循环变量又加一，等于悄悄跳过了一个元素。 - 误区二："所有原地题都套快慢指针"。快慢指针的价值是保序，不是"原地"本身。不保序且删除比例高时，对撞交换的写次数少一个量级；反过来，移动零这类要求稳定性的题用对撞就会破坏相对顺序。
- 误区三："XOR 交换更高级"。
a[i] ^= a[i]这种同索引自交换会把元素直接清零；XOR 只对整数位模式成立，浮点、对象、指针都不适用。Python 的a, b = b, a和 Go 的多重赋值本身就安全，不必炫技。 - 误区四："从前往后搬就行"。把元素整体右移 k 位时，必须从尾部倒着写；从前往后会覆盖还没读到的源数据。标准库的
memmove处理重叠区间，第一步就是判断方向，这个细节常被简写成"从后往前"而忽略前提。 - 误区五："标记法可以随便用"。值域越界、含 0、忘记还原、并发读，都会让负号标记失效或污染数据；同一个位置被取负两次会变回正数，若要统计出现次数，得改用减法或另开计数数组。
- 考点六："复杂度按循环层数数"。三次反转写了三个循环仍然是 O(n)；快慢指针只有一趟，但每保留一个元素都要读一次、写一次。复杂度看的是总操作数，不是循环个数。
实践建议
- 先写不变量，再写循环。把定稿区、垃圾区、未读区的边界写在注释里，
write的初值、循环边界和返回长度都从它推导；写完用随机数组与朴素实现做对拍，并断言a[:write]等于过滤后的结果。 - 选型按需求排序：保序用快慢指针，不保序且删除多用对撞，值域是
1..n用下标标记，整体平移从后往前。不要为了追求 O(1) 空间牺牲可读性——n 很小时新建数组往往更快，缓存更友好、分支更少。 - 工程代码优先用标准库：C++ 的
remove_if配erase、Java 的removeIf、Python 的列表推导加切片赋值。手写原地只在热路径且 profile 证明分配或拷贝是瓶颈时才做，否则维护成本远高于收益。 - 留意别名与副作用：Go 的切片共享底层数组，函数里原地修改会波及所有引用同一数组的切片；Python 切片赋值、NumPy 视图同理。公共函数要么在文档里写明"会修改入参"，要么先复制一份再改。
- 测试用例固定一份清单：空数组、单元素、全删、全留、连续重复、目标值在首尾、k=0 与 k=n、全部相同。每个用例都检查返回长度和尾部残留，很多"看起来对了"的实现在全删或单元素时才露馅。
一句话总结：原地修改的核心不是省内存，而是守住"只有读过的格子才可以覆盖"这条不变量。