算法通关村第三关——双指针的妙用

谁践踏了优雅 2024-03-22 23:28 66阅读 0赞

## 双指针思想 ##

### 快慢指针 ###

> 所谓的双指针其实就是两个变量。双指针思想简单好用，在处理数组、字符串等场景下很常见。看个例子，从下面序列中删除重复元素\[1,2,2,2,3,3,3,5,5,7,8\]，重复元素只保留一个。删除之后的结果应该为\[1,2,3,5,7,8\]。我们可以在删除第一个2时将将其后面的元素整体向前移动一次，删除第二个2时再将其后的元素整体向前移动一次，处理后面的3和5都一样的情况，这就导致我们需要执行5次大量移动才能完成，效率太低。如果使用双指针可以方便的解决这个问题，如图:

![image.png][]

> 首先，定义两个指针slow、fast。slow表示当前位置之前的元素都是不重复的，而fast则一直向后查找，直到找到与slow 位置不一样的（找到不重复的元素）。找到之后就将slow 向后移动一个位置，并肩arr\[fast\] 复制给arr\[slow\]，之后fast继续向后找，循环执行。找完之后，slow以及之前的元素就是单一的了。这样就可以使用一轮移动解决问题。

###  ###

### 对撞型指针 ###

> 上面这种一个指针在前，一个指针在后的方式也称为快慢指针，有些场景需要从两端向中间轴，这种就称为对撞型指针或者叫相向型指针。很多 题目也会用到

###  ###

### 背向型指针 ###

> 还有一种比较少见的背向型，就是从中间向两边走。这三种类型其实非常简单看的只是两个指针是一起向前走 (相亲相爱一起走)，还是从两头向中间走 (冲破干难万险来爱你)，还是从中间向两头走 (缘分已尽，就此拜拜)。

## 删除元素专题 ##

#### 原地移除所有数值等于val的元素 ####

###### 题目 ######

> 给你一个数组nums 和一个值 val ，你需要原地移除所有数字相等的val的元素，并返回移除后数组的新长度。
> 
> 要求;
> 
> 不要使用额外的数组空间，你必须仅使用O(1) 额外空间 并原地修改输入数组。元素的顺序可以改变，你不需要考虑数组汇总超出新长度后面的元素

##### 例子 #####

> 输入: nums = \[3,2,2,3\] , val = 3
> 
> 输出：2
> 
> 输入：nums=\[0,1,2,2,3,0,4,2\] , val = 2
> 
> 输出：5

##### 关键点 #####

> 在删除的时候，从删除位置开始的所有元素都要向前移动，所以这题的关键是如何有很多值为val的元素的时候，避免反复向前移动。

##### 方法一、快慢指针 #####

###### 思想 ######

> 整体思想就是快慢指针。
> 
> 定义两个指针slow和fast，初始值都是0.
> 
> slow之前的位置都是有效部分，fast表示当前要访问的元素
> 
> 以fast为遍历变量，数组遍历的时候，fast不断向后移动：
> 
> 如果nums\[fast\] 的值不为val ，则将其移动到nums\[slow++\]处
> 
> 如果nums\[fast\] 的值为val，则fast继续向前移动，slow先等待。
> 
> 图示：

![image.png][image.png 1]

> 这样一来，前半部分是有效的，后半部分是无效的

###### 代码实现 ######

/**
         * 给你一个数组nums 和一个值 val ，你需要原地移除所有数字相等的val的元素，并返回移除后数组的新长度
         * 要求：
         *  不要使用额外的数组空间，你必须仅使用O(1) 额外空间 并原地修改输入数组。元素的顺序可以改变，你不需要考虑数组汇总超出新长度后面的元素
         * @param nums 给定的数组
         * @param val 要删除的值
         * @return 删除数组元素后的新长度
         */
        public static int removeElements(int [] nums,int val){
            // slow 表示有效的下标（未被删除的下标）
            int slow = 0;
            for (int fast = 0; fast < nums.length; fast++) {
                if (nums[fast] != val){
                    nums[slow] = nums[fast];
                    // 3  2  2  3
                    // 3
                    // nums[0] = num[1]
                    // nums[1] = num[2]
                    slow++;
                }
            }
            return slow;
        }

##### 方法二、对撞双指针 #####

> 对撞指针，也叫交换移除。核心思想是：从右侧找到不是val的值 来顶替（通过交换、覆盖的方式） 左侧是val的值（如果右侧找到为val的值，就将其忽略，直接right--跳过），最后返回左侧不是val的值 。
> 
> 以nums=\[0,1,2,2,3,0,4,2\],val = 2 为例：

![image.png][image.png 2]

> 当left == right时，left以及左侧的就是删除指定元素2 后的所有元素了

###### 实现代码 ######

public static int getremoveElementsSize(int [] nums , int val ){
            int left;
            int right = nums.length -1 ;
            for (left = 0; left <= right ; ){
                if (nums[left] == val && nums[right] != val){
                    int temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;
                }
    
                if (nums[left] != val) {
                    left++;
                }
    
                if (nums[right] == val){
                    right -- ;
                }
    
            }
            return left;
        }

> 对撞型双指针的过程与后面要学习的快速排序是一个思路，快速排序要比较很多轮，而这里只执行了一轮， 理解本题将非常有利于后面理解快速排序算法
> 
> 另外，我们可以发现快慢型双指针留下的元素顺序与原始序列中的是一致的，而在对撞型中元素的顺序和原来的可能不一样了。

#### 删除有效数组中的重复项 ####

###### 题目 ######

> 给你一个 有序 数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。
> 
> 要求：
> 
> 不要使用额外的数组空间，你不需要在原地修改输入数组 并在使用O(1)额外空间的条件下完成

###### 代码实现 ######

/**
         * 给你一个   有序   数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。
         * 要求：
         *      不要使用额外的数组空间，你不需要在原地修改输入数组  并在使用O(1)额外空间的条件下完成
         * @param nums  有序数组
         * @return 数组新长度
         */
        public static  int removeCommonElements(int [] nums){
            // slow 表示可以放入新元素的位置（下标），元素为0的不管
            int slow = 1;
            // 循环起到了快指针的作用
            for (int fast = 1 ; fast < nums.length ; fast ++){
                if (nums[fast] != nums[slow -1]){
                    nums[slow] = nums[fast];
                    slow++;
                }
            }
            return slow;
        }

######  ######

#####  #####

[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/e394fca85f9e407aa6ab38edbde2770a.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/63b91ce5b4054ffd92066335cbaa1426.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/610ede7953e34b389cd0889d1e6c20b7.png