# 双指针


## ***引言***

***对于数组和链表 来说 "双指针"其实是一个常用的解法了***

***双指针也是有很多种类的***

## ***普通双指针***

1. ***什么是双指针***
   - *双指针模式指使用两个一前一后的指针遍历数据结构，直到某个指针触发停止条件*
2. ***使用双指针的好处***
   - *单指针原本需要平方的时间复杂度，用了双指针便可优化到线性时间复杂度*

## ***快慢指针***

1. ***什么是快慢指针***
   - *两个速度不同的指针 比如 "fast指针" 跑两格 "slow指针" 跑一格*
   - *可以拿龟兔赛跑去想象，在一个圆形赛道，"兔子 -> 快指针" 肯定会追上 "乌龟 -> 慢指针"，龟兔赛跑也经常用在判断链表是否成环上面*

## ***左右指针***

1. ***来讲一讲题外话***
   
   - *其实 快慢指针 也有被说成 左右指针，但是本人认为这么说，其实是相当不合理，在此之上，我便有了一丝 朱光潜老先生的 "咬文嚼字" 的感觉，我始终认为 你给一个方法取名 其实就是代表了 你对这个方法的理解*
   - *比如了解什么是左右指针后 你把它叫做 "对撞指针" 也可以 这就是 "1000个读者有1000个哈姆雷特"*
   - *所以我也很推荐你们能拥有自己的想法 不要在意别人的命名 就好比 leetcode 题解 就有把快慢指针说为左右指针，你能说他错吗 其实快慢指针 也确实就是一个指针左 一个指针右*

2. ***什么是左右指针***
   
   - *其实就是一个left指针从最左边向右跑，一个right指针从最右边向左跑*

3. ***左右指针的代码模板***
   
   - ```c
      int left = 0, right = vector.size()-1;
      while (left <= right) {
        ...
      }
     ```
   
   - ```go
      left, right := 0, len(array)-1
      for left <= right {
        ...
      }
     ```

## ***滑动窗口***

1. ***什么是滑动窗口***
   - *滑动窗口是一种基于双指针的一种思想，两个指针指向的元素之间形成一个窗口*
   - *其实可以把它当成一个队列 如果 窗口要向后滑动 直接把开头去掉即可~ 这只是其中一个实现思想*
2. ***滑动窗口的应用场景***
   - *滑动窗口可解决一系列字符串匹配问题*

## ***双指针的应用场景***

1. ***涉及 数组或链表，成对元素的集合、甚至是子数组***
2. ***匹配一个「目标」值或是去除重复***

## ***趣谈 - KMP***

*另起了一个专题*

## ***例题1 - 数组 - 移动零 - 快慢指针***

1. ***题目url***
   
   - *[283. 移动零 - 力扣（LeetCode）](https://leetcode.cn/problems/move-zeroes)*

2. ***其他例题***
   
   - *[26. 删除有序数组中的重复项 - 力扣（LeetCode）](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/)*
   - *[88. 合并两个有序数组 - 力扣（LeetCode）](https://leetcode.cn/problems/merge-sorted-array/)*

## ***例题2 - 数组 - 盛最多水的容器 - 左右指针***

1. ***题目url***
   
   - *[11. 盛最多水的容器 - 力扣（LeetCode）](https://leetcode.cn/problems/container-with-most-water/)*

2. ***解题思路***
   
   - *这道题是 "求最优解", 其实求最优解是 "贪心算法" 和 "动态规划"的场景, 但是这里也可以用双指针*

3. ***其他例题***
   
   - *[189. 轮转数组 - 力扣（LeetCode）](https://leetcode.cn/problems/rotate-array/)*

## ***例题3 - 链表 - 成环链表 - 快慢指针***

1. ***题目url***
   
   - *[141. 环形链表 - 力扣（LeetCode）](https://leetcode.cn/problems/linked-list-cycle/)*

2. ***解题思路***
   
   - *成环链表 用 "快慢指针" 真的人人皆知*
   - *所以也要留个心眼 学个其他的解法 面试的时候 也是个亮点哦*

3. ***其他例题***
   
   - *[142. 环形链表 II - 力扣（LeetCode）](https://leetcode.cn/problems/linked-list-cycle-ii)*

## ***例题4 - 链表 - 反转链表 - 双指针***

1. ***题目url***
   
   - *[206. 反转链表 - 力扣（LeetCode）](https://leetcode.cn/problems/reverse-linked-list/)*

2. ***解题思路***
   
   - 这道题我们可以这么看 **1 -> 2 -> null** 然后变成 **null <- 2 <- 1**
   - *在遍历链表时，将当前节点的 next 指针改为指向前一个节点，由于节点没有引用其前一个节点，因此必须事先存储其前一个节点，在更改引用之前，还需要存储后一个节点。最后返回新的头引用*

## ***例题5 - 字符串 - 无重复字符的最长字串***

1. ***题目url***
   - *[3. 无重复字符的最长子串 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-substring-without-repeating-characters/)*