共计 1663 个字符，预计需要花费 5 分钟才能阅读完成。
一、前言
个别状况下，遍历数组（或者字符串）操作，都是采纳单指针从前往后或者从后往前顺次拜访数组（或者字符串）中的元素。
而对于以下状况，只采纳单指针解决，则会徒增工夫复杂度和空间复杂度：
- 例如：找到两个数使得它们相加之和等于指标数，采纳单指针解决，则须要嵌套循环，使得工夫复杂度增长为 O(n^2)；
- 再例如：翻转数组，采纳单指针解决，则须要额定内存空间，使得空间复杂度增长为 O(n)；
利用双指针技巧则能够优化上述解决方案：
- 第一个例子：能够先对采纳数组进行排序预处理，再创立前后指针向两头遍历，遍历的工夫复杂度为 O(n)，整体工夫复杂度次要取决于排序算法，通常为 O(nlogn)；
- 第二个列子：一个指针负责遍历，另外一个指针负责替换元素，从而使得空间复杂度为 O(1)；
双指针没有简单的定义，总结起来次要解决两类问题：
- 将嵌套循环转化为单循环问题 ；
- 通过指针记录状态，从而优化空间复杂度 ；
上面的实战剖析会让你感触双指针的威力。
二、167. 两数之和 II – 输出有序数组
给定一个已依照升序排列 的有序数组，找到两个数使得它们相加之和等于指标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
这道题目采纳单指针的做法只能通过嵌套循环枚举所有两数之和的办法来解决，工夫复杂度为 O(n^2)。
凑巧本题中的数组曾经是有序数组，那么间接创立前后指针：
- 如果两数之后大于 target，尾指针向前挪动；
- 如果两数之和小于 target，头指针向后挪动；
上述代码利用双指针技巧胜利地将工夫复杂度升高为 O(n)。
三、344. 反转字符串
编写一个函数，其作用是将输出的字符串反转过去。输出字符串以字符数组 char[] 的模式给出。
本题采纳单指针的办法，须要创立一个额定的数组来保留翻转后的元素，空间复杂度为 O(n)。
利用双指针技巧，则能够在遍历的过程中同时实现替换元素的操作，工夫复杂度升高为 O(1)：
雷同类型的题目还有：
- 【345. 反转字符串中的元音字母】
四、141. 环形链表
给定一个链表，判断链表中是否有环。为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。 参考视频：传送门
在链表这种数据结构中，采纳前文所说的前后指针并不一定无效（例如单向链表），这种状况下，双指针的表现形式为： 快慢指针 。
快慢指针指的是：设置两个前进方向雷同但速度不同的指针。
本题中，设置每次挪动一个单位的慢指针和每次挪动两个单位的快指针，那么他们必定会在环内相遇：
雷同类型的题目还有：
- 【26. 删除排序数组中的反复项】
五、125. 验证回文串
给定一个字符串，验证它是否是回文串，只思考字母和数字字符，能够疏忽字母的大小写。阐明：本题中，咱们将空字符串定义为无效的回文串。
回文字符串问题是双指针的经典利用，同时也是面试题中的常客。
六、27. 移除元素
给定一个数组 nums 和一个值 val，你须要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。不要应用额定的数组空间，你必须在原地批改输出数组并在应用 O(1) 额定空间的条件下实现。元素的程序能够扭转。你不须要思考数组中超出新长度前面的元素。
不言而喻的解决办法是通过 while + splice 解决，然而 splice 操作方法是十分耗时的，每次删除元素之后，须要重排数组中的元素 ，具备雷同副作用的操作方法还有 unshift 和 shift。（具体能够查看 V8 源码）
相比拟下，pop 和 push 则是十分快的操作方法，这里能够采纳双指针 + pop 操作方法，进一步优化工夫复杂度：
写在最初
算法作为计算机的基础学科，用 JavaScript 刷，一点也不丢人 ε =ε=ε=┏(゜ロ゜;)┛。
本系列文章会别离给出一种算法的 3 种难度的总结篇（简略难度，中等难度以及艰难难度）。在简略难度中，会介绍该算法的基本知识与实现，另外两个难度，着重解说解题的思路。
如果本文对您有所帮忙，能够点赞或者关注来激励博主。
