双指针法移除数组元素

双指针法移除数组中的指定元素

这里的数组指的是静态数组，是一个内存连续的不可修改大小的数据结构。移除数组中的元素不能够像链表一样直接删除，只能将未被移除的元素前移，形成逻辑上的移除。

移除数组元素时，可以先对数组进行遍历，遍历到需要移除的元素位置时将所有元素往前移动，并记录已经移除的元素数量，最后将数组长度减去移除数量获取到结果数组。而这里组要介绍另一种更加巧妙的方法，能够在时间复杂度为O(n)的情况下解决问题，这里先放一下上面同样的数组用双指针如何解决问题。

光看这张图可能有点云里雾里的，这里详细解释一下上面这个图如何解决移除问题的。

首先我们定义了两个快慢指针slow和fast，他们一起从数组头部向尾部移动。其中，仅当fast指针移动到非移除元素时，将该元素复制到slow指针位置后，两指针一起向后移动（因为在上面数组中，最开始两个指针位于同一位置，所以只需要原地复制即可），若fast指针在需要移除元素上，则只移动fast指针。最终可以在只遍历一次数组的情况下（fast指针遍历一次），就将整个数组需要移除的元素全部移除，最后数组剩余长度即为slow目前所在的位置的大小。

双指针法对应的代码如下：

public class Solution {
    public int RemoveElement(int[] nums, int val) {
        int slow = 0, fast = 0;		// 定义快慢指针
        while(fast < nums.Length){	// 遍历条件为 fast 指针不超过数组长度（防止数组越界访问）
            if(nums[fast] != val){	
                // 当 fast 所在的元素不等于需要移除的元素时
                // 将该元素复制到 slow 指针位置
                // 并将 slow 指针向后移动（可以单独对其进行 +1 操作而不直接使用后置递增）
                nums[slow++] = nums[fast];
            }
            ++fast;		// fast 指针在需要移除的元素上，直接向后移动 fast 指针
        }
        return slow;	// 返回最后剩余的数组长度
    }
}

这段代码可以直接解决力扣中的：27. 移除元素、283. 移动零（将val直接写为0，在符合条件时交换两个指针的元素即可）

移除数组中的重复元素

这里再介绍一道描述不同但方法类似的题目26. 删除有序数组中的重复项

在这道题目中，我们需要进行移除操作的是数组中重复的部分元素而不是指定元素，它的本质还是移除数组元素并保证顺序不发生改变，只是在判断时需要将固定值比较改为重复项比较。在实际操作中，我们仍然将slow指针指向不重复元素数组末尾，通过移动fast指针来进行元素操作，而只有当fast当前所处位置元素与前一个位置元素不相同时才复制到slow指针，明白这一点问题就很好解决了。我们先放一下双指针如何解决问题的GIF图：

下面是对应解决问题的代码，可以对照GIF看一下：

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        if(nums.Length == 0) return 0;	// 当数组长度为 0 时无解
        int slow = 1, fast = 1;			// 定义快慢指针（第一个元素一定包含在结果中，所以直接略过）
        // 当遍历数组内的所有元素
        while(fast < nums.Length){
            // 出现不重复元素时将他复制到 slow 指针所在位置
            if(nums[fast] != nums[fast - 1]){
                nums[slow++] = nums[fast];
            }
            // 将 fast 指针往后移动
            ++fast;
        }
        return slow;
    }
}