1._专题1_双指针_C++

双指针

常见的双指针有两种形式，一种是对撞指针，一种是左右指针。
对撞指针：一般用于顺序结构中，也称左右指针。

• 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
• 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循
  环），也就是：  ◦ left == right （两个指针指向同一个位置）​◦ left > right （两个指针错开）

快慢指针：又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。

这种方法对于处理环形链表或数组非常有用。

其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。

快慢指针的实现方式有很多种，最常用的一种就是：
在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。
 

001 移动零（easy）

「数组分两块」是非常常见的⼀种题型，主要就是根据⼀种划分方式，将数组的内容分成左右两部 分。这种类型的题，一般就是使用「双指针」来解决。

1. 题目链接：283.移动零

2. 题目描述：

3.算法原理

4.C++ 算法代码：

002 复写零（easy）

1. 题目链接：1089.复写零

2. 题目描述：

3.算法原理

4.C++ 算法代码：

003 快乐数（medium）

1. 题目链接：202.快乐数

2. 题目描述：

上面示例图：

 

3.算法原理

4.C++ 算法代码：

004 盛最多水的容器（medium）

1. 题目链接：11.盛最多水的容器

2. 题目描述：

3.算法原理

解法一（暴力求解）（会超时）：

解法二（对撞指针）：

 

4.C++ 算法代码：

005 有效三角形的个数（medium）​

1. 题目链接：611.有效三角形的个数

2. 题目描述：

3.算法原理

 解法一（暴力求解）（会超时）：

解法二（排序 + 双指针）：

​

4.C++ 算法代码：