27. 移除元素

简述一下题目的意思：给你一个数组 nums 和一个值 _val_，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

这个题目的全文太长了，我就不全部挪过来了，就是提示一下这个意思就行了。具体可以去 LC 上查看。

这个题目感觉和 26 题极其相似，我第一个想到的就是“双指针”，第一个指针标记筛后的数组的末位，第二个指针指向筛前数组的开头。然后，两个指针的初始化都在 0，我们这么考虑问题，从筛选前的数字的第一个元素开始，如果这个元素没命中 target 就拷贝到筛选后数组的最后一位，如果命中了，就跳过看第二个元素。

因为筛选用的那个指针移动速度大于等于筛选后的那个指针，所以这个算法会没有重复和遗漏地结束。写出来是：

1
2
3
4
5
6
7
8
9

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i, j = 0, 0
        while j < len(nums):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
            j += 1 
        return i

也是非常短的。写完我看了下答案，原来还有优化的空间，就是我这个算法，拷贝的次数比较多，因为如果整个数组都没有命中的数字，那么每个数字都要被原地赋值一次，确实如此。

如果我们不纠结元素的顺序，可以使用交换法，还是双指针，一个初始化在筛后数字的开头，一个指向筛前数组的末位，就是倒着筛，筛到就交换。这样就极大减少了赋值的次数，提高了效率。很有意思。

知识点：无新的知识点。