题目27. 移除元素 - 力扣LeetCode给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。假设nums中不等于val的元素数量为k要通过此题您需要执行以下操作更改nums数组使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。返回k。示例 1输入nums [3,2,2,3], val 3输出2, nums [2,2,,]解释你的函数应该返回 k 2, 并且 nums 中的前两个元素均为 2。你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。示例 2输入nums [0,1,2,2,3,0,4,2], val 2输出5, nums [0,1,4,0,3,,,_]解释你的函数应该返回 k 5并且 nums 中的前五个元素为 0,0,1,3,4。注意这五个元素可以任意顺序返回。你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。提示0 nums.length 1000 nums[i] 500 val 100题解解题思路方法双指针快慢指针时间复杂度: O(n)空间复杂度: O(1)前提理解题目要求原地移除也就是说不能另外开一个新数组把要保留的元素装进去只能在原来的数组nums上动手。移除的本质是把要保留的元素往前搬覆盖掉要删除的元素然后返回新的长度搬完之后后面多出来的那部分元素是什么并不重要过程定义慢指针slow它指向新数组里下一个要填充的位置初始为 0。同时它也可以理解为当前已经保留的元素个数定义快指针fast它负责从头到尾扫描整个原数组初始也为 0让快指针不断向数组的右边前进可以使用for循环当循环结束时说明整个数组已经遍历完直接返回slow即数组长度程序结束每进入一个循环都要进行以下判断nums[fast] ! val //val为要删除的目标值说明快指针fast所指的这个元素不是目标值val需要保留如何保留呢把它搬到慢指针所在的位置即nums[slow] nums[fast]然后慢指针后移一位slow不符合上面的条件直接印证快指针fast所对应的值刚好为目标值val这个时候快指针fast直接前进而慢指针slow不变这样如果有下一次循环则快指针fast所对应的值直接赋值给慢指针fast所对应的值刚好完成删除数组元素。循环结束时slow的值正好就是与val不同的元素数量也就是题目要返回的k同时可以说是新数组的长度。补充方法相向双指针头尾指针如果数组中等于val的元素很少可以让左右指针从两端往中间夹右指针指向还没处理的那部分的末尾当nums[left] val时就用nums[right]即右边没有问题的元素把这个位置等于val的元素覆盖掉然后right--否则left。它的思想是用尾部不需要保留的元素来填前面的坑能少搬一些元素缺点是会打乱元素的相对顺序图解代码实现伪代码slow 0 for fast 0 to nums.size - 1 { if nums[fast] ! val nums[slow] nums[fast] slow } return slowJava实现class Solution { public int removeElement(int[] nums, int val) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; slow; } } return slow; } }C语言实现int removeElement(int* nums, int numsSize, int val) { int slow 0; for (int fast 0; fast numsSize; fast){ if (nums[fast] ! val){ nums[slow] nums[fast]; slow; } } return slow; }Python实现from typing import List class Solution: def removeElement(self, nums: List[int], val: int) - int: slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow参考代码随想录力扣官方题解题目页里的题解区可以对照快慢指针和相向双指针两种写法OI Wiki算法竞赛向的知识库双指针、二分等专题都有Hello 算法开源算法教程同一份代码有 Java / C / Python 三个版本