双指针算法介绍及使用（上）

1. 算法简介

双指针算法是一种通过使用两个指针（或索引）在数据结构（如数组、链表）中协同遍历来解决问题的技术。通常用于优化时间复杂度，将O(n²)降低到O(n)或O(nlogn)。

2. 常见类型

一般来说，双指针有两种形式，⼀种是对撞（左右）指针，⼀种是快慢指针。

2.1 对撞指针

这种简单来说就是在数组的左右两边各自加上一个指针，然后控制他们从两端向中间移动。比如我们所知道的快速排序，它从代码结构上来说体现了这一点。

2.2 快慢指针

它的核心思路是，使用两个指针（快指针和慢指针），这两个指针在遍历数据结构时速度不同。借助这种速度差，能解决诸如寻找链表中间节点、判断链表是否存在环等问题。

3. 实际使用

3.1 leetcode 283. 移动零

 这道题就是一个快慢指针的实际使用场景，在数组的0和1的位置分别放上慢指针和快指针，

然后分场景判断来实现题目要求。

接下来是其代码实现：

先设置快慢指针fast和slow，然后分条件判断,以下就是判断的条件，然后将表格中的内容写成代码就可以了。

fast	==0	==0	!=0	!=0
slow	==0	!=0	!=0	==0
	fast++	slow++,fast++	slow++,fast++	swep,slow++,fast++

class Solution {
public:void moveZeroes(vector<int>& nums) {int fast=1;int slow=0;while(fast<=nums.size()-1){if(nums[slow]==0&&nums[fast]!=0){swap(nums[slow],nums[fast]);slow++;fast++;}else if(nums[slow]==0){fast++;}else{fast++;slow++;}}}
};

3.2 leetcode 1089. 复写零

 这道题的话难度稍微有一点点高，要使用两次双指针。看题可知，我们要从后往前来遍历（从前往后会覆盖数据），我们先第一次遍历来找到修改完后的最后一位数，然后从后往前遍历即可。

PS:if(end>=n-1)这里不可以写成if(end>n)，原因是边界条件的判断逻辑不同。后者会多判断一次，因为当end在最后一位数的时候end>n的条件还没有满足。简单来说刚刚越界的时候会进入这个判断。

class Solution {
public:void duplicateZeros(vector<int>& arr) {int end=-1;int cur=0;int n=arr.size();while(cur<n){if(arr[cur])end++;elseend+=2;if(end>=n-1)break;cur++;}if(end==n){end--;arr[end--]=0;cur--;}while(cur>=0){if(arr[cur]!=0){arr[end]=arr[cur];cur--;end--;}else{cur--;arr[end--]=0;arr[end--]=0;}}}
};