双指针是指用两个引用或者索引，或者某种键为主的操作手段，在很多场景有重要的应用，比如链表。有些时候还能成为比较巧妙的解题手段。今天就来总结一下双指针的使用。
双指针的套路
根据不同的场合和用法，双指针可以分为同向双指针和对撞指针。
同向双指针
又可以细分为滑动窗口，以及快慢指针。
滑动窗口
两个指针，通常一个慢一个快，之间的子数组具有某种特质，快指针（也称右指针）正常向前遍历，新元素会加入，同时左指针也会向前移动，就像一个向前开动的公交车一样。
有些窗口大小是固定的，有些则是不固定的，看具体情况而定，新元素进入以及窗口中的元素移出窗口也要视题目中的具体条件而定。
典型问题
| 题目 | 题解 | 要点说明 |
|---|---|---|
| 3. 无重复字符的最长子串 | 题解 | 滑动窗口 |
| 76. 最小覆盖子串 | 题解 | |
| 209. 长度最小的子数组 | 题解 | 滑动窗口，双指针 |
| 239. 滑动窗口最大值 | 题解 | |
| 438. 找到字符串中所有字母异位词 | 题解 | 滑动窗口，哈希表 |
| 567. 字符串的排列 | 题解 | 经典滑动窗口 |
| 713. 乘积小于 K 的子数组 | 题解 | 滑动窗口，双指针 |
| 904. 水果成篮 | 题解 | 滑动窗口 |
| 1604. 警告一小时内使用相同员工卡大于等于三次的人 | 题解 | 如何正确的转化为滑动窗口， 以及如何实现滑动窗口 |
| 1004. 最大连续1的个数 III | 题解 | 非固定长度的滑动窗口，有明确的约束条件 |
| 1493. 删掉一个元素以后全为 1 的最长子数组 | 题解 | 同1004 |
| 1456. 定长子串中元音的最大数目 | 题解 | 滑动窗口板子 |
| 题解 | ||
| 题解 | ||
| 题解 |
快慢指针
最为经典的场景就是解决一坨单链表问题，比如找链表的中间节点，或者找环，以及归并等等。
此外，快慢指针也常用于数组，通常是涉及数组的元素移动，此类型的要点就是一个指针正常遍历原数组，此为快指针，一个指针用指向结果数组，快指针正常遍历，慢指针依据某些条件才向后移动。
对撞指针
就是一个从前往后遍历，一个从后往前遍历，循环中止条件是两指针相遇，通常用在二分查找，回文相关，反转数组列表，或者其他场合。
双指针技巧
双指针，除了以上几种比较典型之外啊，其实也挺宽泛的，只要用了两个以上的指针（下标）就算得上是双指针，也没啥固定的模式。
但有时，有两个常见的技巧能大幅优化效率和代码，一个就是逆向思维，比如一些涉及归并的题目中，如果用常规思路，从前往后，可能用额外空间才可以，但如果从后往前，或者从两头往中间，可能就打开了一片新天地。这里的正向和逆向视具体情况而定，比如有些归并类的是直觉上是从前往后，那这就是正向，从后往前则是逆向；再如一些中间分段的数组如山峰或者山谷形的，从间往往两头是正向，那从两头往中间则逆向。如题977。
还有一个技巧是，如果要求返回数组的顺序由原数组决定，但数据 的选择由计算规则确定，也就是说我们是在计算后的数组上应用双指针进行选择，但又要返回原数据中的数据顺序，这时呢，其实可以不必直接用双指针在计算后的数组中选择结果，可以先行移动指针到目标范围，然后再遍历去选择结果。典型的问题是题658。
典型问题
| 题目 | 题解 | 要点说明 |
|---|---|---|
| 19. 删除链表的倒数第 N 个结点 | 题解 | 经典快慢指针 |
| 189. 轮转数组 | 题解 | |
| 557. 反转字符串中的单词 III | 题解 | |
| 658. 找到 K 个最接近的元素 | 题解 | 先移指针到目标范围，再选择结果 |
| 876. 链表的中间结点 | 题解 | 经典快慢指针 |
| 915. 分割数组 | 题解 | |
| 977. 有序数组的平方 | 题解 | 逆向思维 |
| 1813. 句子相似性 III | 题解 | |
| 面试题 01.05. 一次编辑 | 题解 | |
| 2042. 检查句子中的数字是否递增 | 题解 | |
| 2309. 兼具大小写的最好英文字母 | 题解 | |
| 题解 | ||
| 题解 | ||
| 题解 |
高难度双指针
有些题目涉及一个数组或者列表中的三个相互约束的元素时，并且，每个下标位置的值是固定的，这种情况，也可以用双指针。三个元素相互约束的意思是指，想要求得某一元素的值，它会受制于它前面的某一个约束条件（比如最值）以及它后面的一个约束条件（比如最值），每个位置的值是固定的意思是，一旦找到约束条件，能计算此位置的值后，它不会再受其他条件影响而变化，也就是说一个位置遍历过后，不用再次遍历去求值。这种题目，一般可以用双指针来优化，其实是对撞指针，一个从前向后，一个从后向前，两指针相遇，遍历结束。典型代表是题11和题42。
这种题目，需要厘清题目，找出会相互制约的三个元素，也就是说数组中会有三个元素相互制约，但想要证明双指针是正确的却有点困难。可以当作一种套路来记得，如果有类似的题目，可以往上面套一套。
典型问题
| 题目 | 题解 | 要点说明 |
|---|---|---|
| 11. 盛最多水的容器 | 题解 | 对撞指针 |
| 42. 接雨水 | 题解 | |
| 167. 两数之和 II - 输入有序数组 | 题解 | 经典对撞指针 |
| 1679. K 和数对的最大数目 | 题解 | |
| 题解 | ||
| 题解 |