移除元素 - 双指针

---

---

力扣原题: link

题目：

例子：

前言

许多小伙伴在解这题的时候，都会直接采用暴力解法，即

class Solution {
    
public:
    int removeElement(vector<int>& nums, int val) {
    
        int size=nums.size();
        for(int i=0;i<size;++i)
        {
    
            if(val==nums[i])     //如果在数组中查找到需要目标元素
            {
    
                for(int j=i+1;j<size;++j)
                {
    
                    nums[j-1]=nums[j];      //数组元素前移
                }
                i--;        //因为下标i以后的数值都往后移动了一位，所以i也需移动
                size--;     //数组个数-1
            }
        }
        return size;
    }
};

从双层循环就可以看出这很暴力，但是大家有没有想过如何使用一层for循环来实现呢，让解题变得高效又快速。接下来，就给小伙伴们讲讲这题如何用双指针来实现

---

一、什么是双指针？

双指针即快指针与慢指针，利用双指针可以通过一个for循环来实现两层for循环，即用O(n)代替O(n²)

快指针：用来获取新数组中的元素，即不包含需查找的元素
慢指针：获取新数组中需要更新的位置

二、双指针思路流程

第一次写博客，不知道动画怎么上传，就以图片的形式呈现给大家

①首先双指针均指向首元素

②双指针一同偏移

③找到待删元素2

④快指针偏移，但慢指针不动

⑤将此时慢指针所保留的目标元素替换成快指针所指向的新元素的值

⑥没有找到目标元素，则双指针移动向后移动

⑦在没找到下一个待删元素前， 不停地做替换以及指针偏移操作

⑧同上

⑨ 最后返回的是慢指针当前所指下标是因为它之前刚好是删除完元素的个数

三、代码实现

代码如下（示例）：

class Solution {
    
public:
    int removeElement(vector<int>& nums, int val) {
    
        int fast;       //快指针 - 获取新数组中的元素
        int slow=0;     //慢指针 - 获取新数组中需要更新的位置
        for(fast=0;fast<nums.size();++fast)     //快指针的遍历
        {
    
            if(nums[fast]!=val)     //当数组元素与所查元素不相等时，元素更新
            {
    
                nums[slow]=nums[fast];          //相等于删除操作 - 赋值
                slow++;             //慢指针的移动
            }
        }
        return slow;
    }
};

疑难解析：
①这里是只用到了一层for循环，用于快指针的遍历操作，首先，开始判断第一个元素，快指针所指向的值不等于我们所需要删除的目标元素，则更新新数组，把快指针所获取的值赋给慢指针所在的位置。

②在双指针移动的过程中，一旦找到我们需要删除的目标原则，则不进入这一段if判断

         if(nums[fast]!=val)    
         {
    
             nums[slow]=nums[fast];       
             slow++;             
         }

在这时只有快指针在移动，而慢指针则停止移动，也就是说只有外层的for循环一直在向后遍历。接着到下一个又找到不同元素，开始赋值操作，也就是说相当于把慢指针所在位置的元素替换成快指针此时指向的元素,然后让慢指针也进行一个偏移，使得慢指针与快指针始终是保持一个下标的距离

③其实这个慢指针的偏移，可以放入数组的赋值中，即

         if(nums[fast]!=val)    
         {
    
             nums[slow++]=nums[fast];                 
         }

这样是不是看起来更精练了呢

---

总结

本题的时间复杂度为O(n),空间复杂度为O(1)。双指针法在对于数组的操作中还是很实用的，不仅是有快慢指针，还有那种左右指针相对遍历，可以确保移动最少的元素，这里就不在赘述，有兴趣的小伙伴可以去了解一下。

其他版本及相似题目

一、Java

class Solution {
    
    public int removeElement(int[] nums, int val) {
    

        // 快慢指针
        int fastIndex = 0;
        int slowIndex;
        for (slowIndex = 0; fastIndex < nums.length; fastIndex++) {
    
            if (nums[fastIndex] != val) {
    
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;

    }
}

二、JavaScript

var removeElement = (nums, val) => {
    
    let k = 0;
    for(let i = 0;i < nums.length;i++){
    
        if(nums[i] != val){
    
            nums[k++] = nums[i]
        }
    }
    return k;
};

三、Python

class Solution:
 	 def removeElement(cls, nums: List[int], val: int) -> int:
        fast = slow = 0

        while fast < len(nums):

            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1

            # 当 fast 指针遇到要删除的元素时停止赋值
            # slow 指针停止移动, fast 指针继续前进
            fast += 1

        return slow

相关题目推荐
26.删除排序数组中的重复 link

283.移动零 link

---

最后很感谢大家的观看，如果有不好的地方请指正，如果觉得可以记得点个赞再走哦️