【LeetCode】27.移除元素

题目：
移除元素

• 原地移除指定的元素
• 返回移除后数组的长度；且前n位须是移除后的元素

思路：
需要原地移除，那么就不能使用额外的空间，即空间复杂度是。
这个时候可以考虑双指针，慢指针i，快指针j。只需要把指针j != val的元素复制给位置i，即前i个元素即为删除指定元素val后的元素，移除后数组的长度即为i。

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

怎么利用移除后的元素顺序可以改变这一条件呢？
也可以利用对撞指针的思想，一个指针i指向头，一个指针j指向尾。当nums[i] == val，交换nums[i],nums[j]。

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