什么是数组原地操作？为什么常用双指针覆盖？

简化版

数组原地操作指在原数组上完成修改，额外空间通常要求 O(1)。常见套路是读指针扫描原数组，写指针维护下一个要写的位置，例如删除指定元素、移动零、去重和分区。

详细版

数组不能像链表一样 O(1) 删除中间节点，直接删除通常要搬移元素。很多面试题要求“原地修改”，本质是用覆盖代替频繁删除：

read 扫描每个元素
write 指向下一个保留位置
符合条件就 a[write++] = a[read]

这样只遍历一次，时间 O(n)，额外空间 O(1)。注意原地操作通常只保证前 write 个位置有效，后面的旧值不用管，除非题目要求清理。

完整版教学

一、原地操作的目标是少开额外空间

数组题经常要求 in-place，也就是尽量在原数组上改，不额外创建同规模数组。

输入:  [3, 0, 2, 0, 5]
输出:  [3, 2, 5, 0, 0]
额外空间: O(1)

原地不代表完全不使用变量，几个指针、计数器、临时变量都可以。它强调的是不要再开一个 O(n) 的辅助数组。

记忆钩子：原地操作不是不用空间，而是不用随 n 增长的大空间。

二、为什么数组适合覆盖写

数组按下标访问 O(1)，所以我们可以用一个写指针维护“有效区”的末尾。

以删除所有值为 0 的元素为例：

int write = 0;
for (int read = 0; read < n; read++) {
  if (a[read] != 0) {
    a[write++] = a[read];
  }
}

扫描结束后，[0, write) 是保留下来的元素。[write, n) 里是什么不重要，除非题目要求填充。

这个模式避免了每遇到一个要删除元素就整体左移。

三、数字例子看覆盖过程

数组：

a = [3, 0, 2, 0, 5]

执行过程：

read	a[read]	write 前	动作	有效区
0	3	0	写 a[0]=3，write=1	[3]
1	0	1	跳过	[3]
2	2	1	写 a[1]=2，write=2	[3,2]
3	0	2	跳过	[3,2]
4	5	2	写 a[2]=5，write=3	[3,2,5]

最后有效长度是 3。这个过程只移动需要保留的元素，且最多写 n 次。

四、常见变体是移动零

移动零要求保留非零元素相对顺序，并把零放到末尾。

int write = 0;
for (int read = 0; read < n; read++) {
  if (a[read] != 0) {
    a[write++] = a[read];
  }
}
while (write < n) {
  a[write++] = 0;
}

前半段压缩非零元素，后半段补零。时间 O(n)，额外空间 O(1)，相对顺序不变。

这类题的关键不是“删除”，而是“重建前缀有效区”。

五、分区类问题也用双指针

有些原地操作不是稳定覆盖，而是左右交换。例如把奇数放左边、偶数放右边。

int l = 0, r = n - 1;
while (l < r) {
  while (l < r && a[l] % 2 == 1) l++;
  while (l < r && a[r] % 2 == 0) r--;
  int tmp = a[l];
  a[l] = a[r];
  a[r] = tmp;
}

这种方式不保证原相对顺序，但交换次数少。面试要看题目是否要求稳定顺序，稳定和不稳定会影响算法选择。

六、原地操作的边界要说清

很多原地题返回的是新长度，而不是要求数组物理长度变化。数组长度固定，无法真正“变短”。

input:  [1, 1, 2, 3, 3]
output: first k elements [1, 2, 3]
k = 3
tail values ignored

如果题目要求后缀置零、置空或保持某种顺序，要额外处理；如果没有要求，不要浪费时间清理无效区。

七、常见误区与追问

误区：原地操作就是不能用任何变量。 可以用常数个变量，禁止的是 O(n) 辅助数组。
误区：删除数组元素会让数组长度变短。 普通数组长度固定，通常返回新有效长度。
误区：覆盖写一定保持所有元素原样。 覆盖会改变后缀旧值，题目一般只关心有效前缀。
追问：稳定和不稳定原地分区有什么区别？ 稳定保相对顺序，常用覆盖；不稳定可左右交换，移动次数少。
追问：为什么双指针能做到 O(n)？ read 每个元素最多访问一次，write 只随保留元素前进。
追问：什么时候需要清理尾部？ 题目明确要求移动零、释放引用或避免内存泄漏时需要。

八、加强记忆

数组原地题记成“读指针扫描，写指针建有效区”。删除、去重、移动零都可以用覆盖写；分区题可以用左右指针交换。原地的空间要求是 O(1)，不是一个变量都不能用；数组物理长度不会变，很多题返回的是新有效长度，后缀是否清理看题目要求。

简化版

详细版