这是我参与新手入门的第3篇文章

一、题目描述

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

二、思路分析

• 因为不能借助于其他变量，这里我们就需要用打标记的方法来进行区分，循环使我们无法避免的方式我们需要在循环的过程中将当前变量进行标记下，然后决定是否是进行删除，删除很简单我们不需要管理，等待下一次的清洗就可以了。剩下的就是不需要删除那么就需要保留，而保留在本题是就需要进行移位，移动到哪一个索引中这就需要我们另外在标记下当前最新索引值。

• 针对上述提到的两个指针我们可以叫做【双指针】或者叫做【快慢指针】。

• 显然，由于数组已经排序，所以重复的元素一定连在一起，找出它们并不难，但如果毎找到一个重复元素就立即删除它，就是在数组中间进行删除操作，整个时间复杂度是会达到 O(N^2)。

• 简单解释一下什么是原地修改：

• 如果不是原地修改的话，我们直接 new 一个 int[] 数组，把去重之后的元素放进这个新数组中，然后返回这个新数组即可。

• 但是原地删除，不允许我们 new 新数组，只能在原数组上操作，然后返回一个长度，这样就可以通过返回的长度和原始数组得到我们去重后的元素有哪些了。

• 这种需求在数组相关的算法题中时非常常见的，通用解法就是我们前文 双指针技巧 中的快慢指针技巧。

三、AC 代码

public int removeElement(int[] nums, int val) {
    int n = nums.length;
    if (n == 0) {
        return n;
    }
    int left = 0;
    for (int right = 0; right < n; right++) {
        if (nums[right] != val) {
            nums[left] = nums[right];
            left++;
        }
    }
    return left;
}
复制代码

四、总结

• 本题考查重点就是我们对快慢指针的运用。借助两个指针可以记录我们需要进行移位过程中的变量。巧妙解决问题