【双指针】对撞指针 快慢指针 移动零
文章目录
- 双指针介绍
- 对撞指针
- 快慢指针
- 283. 移动零
- 解题思路
- 算法思路
- 算法流程
双指针介绍
算法中的双指针，并不一定是指我们平常在 c/c++ 使用的指针类型，更多时候其实是数组的下标等，因为它们也是有标识某个元素的功能，通常我们也就顺其自然地称其为 “指针” ！
常见的双指针有两种形式，一种是对撞指针，一种是快慢指针。
对撞指针
一般用于顺序结构中，也称为左右指针。对撞指针 从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
对撞指针的 终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
left == right（两个指针指向同一位置）left > right（两个指针错开）
快慢指针
又称为龟兔赛跑算法，其基本思想就是 使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理环形链表或数组非常有用！
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。快慢指针的实现方式有很多种，最常用的一种就是：
- 在一次循环中，每次 让慢的指针向后移动一位，而 快的指针往后移动两位，实现一快一慢。
283. 移动零
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。