算法基础：双指针法处理数组分块问题

双指针算法与数组分块

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

约束条件

• 必须在原数组上操作（不复制数组）。
• 尽量减少操作次数。
• 保持非零元素的相对顺序。

核心思路

本题属于典型的数组分块题型。所谓数组分块，即根据特定规则将数组划分为不同的区间，并通过维护这些区间的特征来解决问题。对于此类问题，双指针算法是最优解之一。

双指针中的'指针'指的是数组下标。我们可以利用两个指针将数组划分为三个逻辑区域：

1. 已处理非零区：存放已确认的非零元素，保持原有相对顺序。
2. 已处理零区：存放已确认的零元素（通常位于非零区之后）。
3. 未处理区：尚未遍历的元素。

具体实现时，定义两个指针：

• dest：指向下一个非零元素应该放置的位置。
• cur：当前遍历到的元素索引。

算法流程

1. 初始化 dest = -1，cur = 0。
2. 遍历数组，当 cur 遇到非零元素时：
   • dest 自增 1。
   • 交换 nums[dest] 和 nums[cur]。
   • cur 继续向后移动。
3. 若 cur 遇到零元素，直接跳过，因为零元素会被留在后面自然形成零块。
4. 遍历结束后，所有非零元素已按序排列在前部，剩余部分自动为零。

代码实现

public class Solution {
    public void moveZeroes(int[] nums) {
        int dest = -1; // 指向已处理非零区的最后一个位置
        int cur = 0;   // 当前遍历指针
        
        while (cur < nums.length) {
            if (nums[cur] != 0) {
                dest++;
                // 交换非零元素到指定位置
                   nums[dest];
                nums[dest] = nums[cur];
                nums[cur] = temp;
            }
            cur++;
        }
    }
}