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

1. 算法简介

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

2. 常见类型

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

2.1 对撞指针

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

2.2 快慢指针

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

3. 实际使用

3.1 leetcode 283. 移动零

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

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

接下来是其代码实现：

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

class Solution {public: void moveZeroes(vector& 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& arr) { int end=-1; int cur=0; int n=arr.size(); while(cur=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; } } }};