数组原地操作：快慢指针与模拟

很多数组题目都带着一个硬性要求：空间复杂度 O(1)，不许开新数组。数组又不能像链表那样改指针，怎么办？答案是让指针来"划地盘"：用两个下标把数组人为分成"已处理区"和"未处理区"，边扫边覆盖。这篇文章用四道经典题把原地操作的套路讲透。

原地移除元素（LeetCode 27）快慢指针逐行讲解

题目：原地删除数组中所有值等于 val 的元素，返回新长度 n，要求前 n 个位置是保留的元素，顺序可保持，剩余内容无所谓。

数组删不掉元素，只能把要保留的元素搬到前面覆盖掉要删的。用两个指针分工：

public int removeElement(int[] nums, int val) {
    int slow = 0;   // slow 指向"已保留区"的下一个空位：[0, slow) 都是 != val 的元素
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {        // fast 扫到该保留的元素
            nums[slow] = nums[fast];    // 搬到保留区的空位上
            slow++;                     // 保留区扩一格
        }
        // nums[fast] == val 时什么都不做，直接跳过
    }
    return slow;    // [0, slow) 就是最终保留的元素个数
}

逐行拆解不变量：任意时刻，[0, slow) 区间内全是不等于 val 的元素，且它们恰好是原数组前 fast+1 个元素中该保留的那些。

fast 每轮前进一格，负责"看"：是保留对象就交给 slow，不是就跳过。
slow 每轮最多前进一格，负责"放"：永远指向下一个可以覆盖的位置。
循环结束后 [slow, end) 全是 val 或被覆盖的残渣，题目说了无所谓，所以直接返回 slow。

复杂度：fast 走一遍 O(n) 时间，O(1) 额外空间。模拟一遍 nums = [3,2,2,3], val = 3：

fast=0  3==val 跳过          [3,2,2,3]  slow=0
fast=1  2 保留 → 覆盖 nums[0] [2,2,2,3]  slow=1
fast=2  2 保留 → 覆盖 nums[1] [2,2,2,3]  slow=2
fast=3  3==val 跳过          [2,2,2,3]  slow=2
返回 2，前两位 [2,2] ✓

变形：移动零（LeetCode 283）

题目：把所有 0 移到数组末尾，同时保持非零元素的相对顺序，要求原地。和 27 只差一句话——"删掉 val"变成了"删掉 0，并把 0 堆到尾部"：

public void moveZeroes(int[] nums) {
    int slow = 0;   // [0, slow) 全是非零元素，且保持原相对顺序
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            nums[slow++] = nums[fast];   // 非零元素前移
        }
    }
    // 把 [slow, end) 填回 0
    while (slow < nums.length) {
        nums[slow++] = 0;
    }
}

一个更聪明的写法是交换版：非零元素不是"搬过去"，而是和 slow 位置"换过来"——这样 slow 位置原本的 0 自动被换到后面，省掉最后的回填循环：

public void moveZeroes(int[] nums) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            if (slow != fast) {              // 自交换可跳过
                int t = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = t;
            }
            slow++;
        }
    }
}

两版都是 O(n)/O(1)。注意保持非零元素相对顺序的来源：fast 从左到右扫描，非零元素按原顺序依次落位，顺序天然保留。

有序数组平方（LeetCode 977）两端向中间

题目：非递减数组（可含负数），返回每个数平方后仍非递减的数组。要求 O(n)。

关键观察：负数平方后反而变小，平方后的最大值一定出现在数组两端（最左的强负数或最右的正数），最小值在中间。既然最大值在两端，就从两端往中间走，把较大者从结果数组的尾部往前填：

public int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];          // 本题允许开结果数组（返回值本身）
    int left = 0, right = n - 1;     // 分别指向窗口两端
    int pos = n - 1;                 // 从结果尾部往前填
 
    while (left <= right) {
        int sqL = nums[left] * nums[left];
        int sqR = nums[right] * nums[right];
        if (sqL > sqR) {
            ans[pos--] = sqL;        // 左端平方更大，占当前最大位
            left++;                  // 左端收缩
        } else {
            ans[pos--] = sqR;
            right--;                 // 右端收缩
        }
    }
    return ans;
}

考点拆解：

如果无脑"先平方再排序"，是 O(nlogn)；双指针利用原数组有序性，一趟 O(n) 完成，这就是题目设 O(n) 要求的意义。
从尾部往前填是本题最巧的一步：从大到小落位，避免了"最小值在中间找不到"的尴尬。如果从头部填，你每次都不知道下一个最小值在左半还是右半。
这道题的双指针是相向而行（两端向中间），与 27 的同向快慢指针形成对照：同向管"分区覆盖"，相向管"两端择优"。

螺旋矩阵 II（LeetCode 59）边界收缩四步循环

题目：生成 n×n 矩阵，按顺时针螺旋填入 1 到 n²。纯模拟题，难点不在算法而在边界规则的自洽：一圈有四条边，每条边填到哪、跳过哪个角，稍不留神就重复或漏格。

统一规则：每条边左闭右开——填起始格，不填末尾格（末尾格归下一条边填）。四个偏移量 d、d2、d3、d4 标记四条边的终点：

public int[][] generateMatrix(int n) {
    int[][] ans = new int[n][n];
    int loop = n / 2;          // 完整圈数，n 为奇数时中心格单独填
    int start = 0;             // 每圈起始格 [start][start]
    int count = 1;             // 当前要填的数
    int i, j;
 
    while (loop-- > 0) {
        i = start; j = start;
        // 第 1 步：上边，从左到右，左闭右开，终点是 [start][n-start-1] 之前的格
        for (; j < n - start - 1; j++)   ans[i][j] = count++;
        // 第 2 步：右边，从上到下，行进 i，终点是 [n-start-1][n-start-1] 之前
        for (; i < n - start - 1; i++)   ans[i][j] = count++;
        // 第 3 步：下边，从右到左，终点是 [n-start-1][start] 之前
        for (; j > start; j--)           ans[i][j] = count++;
        // 第 4 步：左边，从下到上，终点是 [start][start] 之外
        for (; i > start; i--)           ans[i][j] = count++;
        start++;               // 圈层内缩一格
    }
 
    if (n % 2 == 1) {
        ans[n / 2][n / 2] = count;   // 奇数阶矩阵的中心格
    }
    return ans;
}

自洽性检查（以 n=4 第一圈为例）：上边填 [0][0..2]（3 格，[0][3] 留给右边），右边填 [0..2][3]（[3][3] 留给下边），下边填 [3][3..1]（[3][0] 留给左边），左边填 [3..1][0]（回到起点附近停止）。每格恰好填一次，四步无缝衔接——这就是"左闭右开"的价值：不需要每步再打补丁判断角格。

复杂度：每格填一次，O(n²) 时间；除结果矩阵外 O(1) 额外空间。

原地操作通用心法

四道题做下来，提炼出原地操作的双指针心法：

手法	指针运动	不变量（已处理区定义）	代表题
同向快慢指针	同起点同方向，fast 快 slow 慢	`[0, slow)` 是保留区	27、283
相向双指针	两端向中间收缩	两端窗口内是"未决策区"	977
边界收缩	四条边循环 + 圈层内缩	外圈已填完，内圈待填	59

三条心法：

先定义不变量，再写代码。动笔前用一句话说清"指针划分的两个区间各是什么"，循环体里的每个赋值都必须维护这句话。边界写错，九成是不变量没定义清楚。
覆盖优先于交换，交换优先于开新数组。27 用覆盖就够；需要保序且尾部有要求（如 283）用交换；真的需要返回新数组时才开（977）。
用极端用例验证：空数组、单元素、全是要删的值、全是保留的值、n=1 的矩阵。原地操作最容易在这些点翻车。

对应 LeetCode 题目

题号	题名	一句话考点
27	移除元素	快慢指针原地覆盖的模板题
283	移动零	快慢指针 + 交换/回填两种写法
977	有序数组的平方	相向双指针，结果从尾部填充
59	螺旋矩阵 II	四步循环 + 左闭右开边界模拟
26	删除有序数组中的重复项	快慢指针变体：与"上一个保留值"比较

参考

代码随想录 · 数组专题