27_移除元素

类型：数组

1. 移除元素 💚
https://leetcode-cn.com/problems/remove-element/

❓ 移除数组 nums 中所有值为 val 的元素，返回移除后的数组的长度。

💡 同向双指针

left、right 指针均从数组首向尾部移动。
- 如果 right 指针指向的元素不等于 val，则它应该在输出数组里，将 right 指向的元素赋值给 left，然后将 left 和 right 同时右移。
- 如果 right 指向的元素等于 val，则它不能在输出数组里，left 指针不动，right 右移一位。
整个过程中，[0, left) 中的元素都不等于 val.
```
class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
}
```
时间复杂度：O(n)，数组至多遍历两次。空间复杂度：O(1)

💡 逆向双指针

（此方法会改变数组，并且会改变元素间顺序。）

left、right 指针从两端向中间移动。
- 如果 left 指向的元素等于 val，则将 right 指向的元素赋值给 left 指向的元素。同时 right 左移一位。
- 如果赋值过来的元素恰好也等于 val，则可以重复上一个操作。直到 left 指向的元素不等于 val 了，则 left 右移一步。
- left 与 right 重合时，遍历结束。[0, left) 中的元素都不等于 val.
时间复杂度：O(n)，数组只遍历一次。空间复杂度：O(1)