【硬核算法】用动画和实例的方式打开双指针问题

大家好，我是袁厨。就是那个酷爱做饭自己考取了厨师资格证的程序员，文章中喜欢放动图的袁厨。

今天给大家带来双指针的详细解析，大家记得打卡啊。在我们做题的时候很多题目都可以用双指针解决，所以我们在刷题初期这个是必须掌握的，而且要牢固。下面我们通过一些例子帮助我们理解双指针思想。下面的例子不是很难但很经典，我们一起看下去吧。

二分查找

说到双指针，就不得不说二分查找这个经典算法啦，二分查找的核心就是双指针，下面我们一起来回顾一下二分查找。

小明：小红你猜一下我买的新衣服多少钱。

小红：300

小明：贵了

小红：150

小明：便宜了

小红：225

小明：恭喜你猜对了。

小明买了一个新衣服去找小红显摆，让小红猜他的衣服价格，我想各位同学应该都玩过这个游戏吧。然后小红猜过之后，小明告诉小红是贵了还是便宜了。这个小游戏就和我们的二分查找类似，哇，我们很小的时候就学会了这个算法了吗？

下面我们一起来把二分查找给解决了吧！

注：二分查找的前提是线性表的记录必须是有序的

了解二分查找代码之前我们先了解一下顺序表查找，即遍历数组，先让我们对遍历查找有所了解。

上面的代码实现了遍历查找，代码很简单，思路也很简单，下面我们来看二分查找的主要思路

我们想查找元素 5 的位置，下面我们来说一下二分查找的具体查找过程。如上图所示，我们首先定义两个指针，分别在数组头部和尾部。然后找出指针的中间位置，将中间元素的值和目标元素进行对比，进而决定我们是移动左指针还是右指针。

mid = 0 + （9-0）/ 2 =  4 , nums[4] = 9 是大于我们的目标值，所以我们需要移动右指针，则 right = mid - 1。

移动完之后我们发现目标值还是在我们左指针和右指针的区间里的。我们继续进行查找，继续执行上述过程。判断移动左指针还是右指针，进行查找目标值。下面我们动图来描述所有过程吧。

二分查找视频

二分查找代码

是不是感觉好像一个男生一个女生慢慢走近的过程，哈哈哈哈，好尬啊。

好啦，经典的二分查找我们已经描述完了，下面我们看一下，如何利用双指针思想解决实际问题。

35.搜索插入位置

题目描述

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2

示例 2:

输入: [1,3,5,6], 2
输出: 1

示例 3:

输入: [1,3,5,6], 7
输出: 4

示例 4:

输入: [1,3,5,6], 0
输出: 0

题目解析

这个题目是经典的双指针题目，刚才我们描述了二分查找的思想，该题的思路二分查找思路一样，只不过是多加了一些规则而已。

我们通过阅读题目和示例我们可以知道，搜索插入位置，那么我们返回值也无非有四种情况

（1）比数组里的任何值都小，插入头部

（2）比数组里的任何值都大，插入尾部

（3）查询到数组元素，返回该处索引值

（4）数组内无该元素，将其插入两元素之间。

见下图

既然我们了解了所有情况，那岂不是一次 AC 了呀，我们来看一下代码的执行过程。

题目代码

27.移除元素

上面那个题目我们使用了两头起步的双指针思想解决了搜索插入位置这个题目，下面我们继续来一个新类型的双指针，不知道他有没有名字（如果有名字，在下面讨论告诉我呀），暂且称之为侦察兵双指针。让我们一起看下去吧，这个侦察兵双指针到底是什么东东。

题目描述

给你一个数组  nums  和一个值  val，你需要 原地 移除所有数值等于  val  的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用  O(1)  额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3

函数应该返回新的长度  2, 并且  nums  中的前两个元素均为  2  你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定  nums = [0,1,2,2,3,0,4,2],  val = 2,

函数应该返回新的长度  5, 并且  nums  中的前五个元素为  0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

题目解析

下面我们来看一下具体思路，创建两个双指针，从数组头部出发，前面的指针负责侦察找到待删除的元素，遇到待删除结点时，前面指针移动，后面不动，等前指针越过待删除元素时，后面的指针继续移动。直至遍历结束，我们可以这样理解这个组合，运行时前指针负责探路，没有危险时后指针跟上，所以我叫他侦察兵。该类型的双指针多用于删除结点时的题目，在链表中同样适用，大家可以去做一下 leetcode 上的83题和84题。（如下图）

解题思路大家已经了解了，下面我们来看一下如何代码的执行过程吧.

题目代码

209，长度最小的子数组

我们下面再看一种新类型的双指针，也就是我们大家熟知的滑动窗口。这也是我们做题时经常用到的，下面我们来看一下题目吧！

题目描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s  =  7, nums  =  [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

题目解析

滑动窗口：就是通过不断调节子数组的起始位置和终止位置，进而得到我们想要的结果，滑动窗口也是双指针的一种。

下面我们来看一下这道题目的做题思路，其实原理也很简单，我们创建两个指针，一个指针负责在前面探路，并不断累加遍历过的元素的值，当和大于等于我们的目标值时，后指针开始进行移动，判断去除当前值时，是否仍能满足我们的要求，直到不满足时后指针 停止，前面指针继续移动，直到遍历结束。是不是很简单呀。前指针和后指针之间的元素个数就是我们的滑动窗口的窗口大小。见下图

好啦，该题的解题思路我们已经了解啦，下面我们看一下，代码的运行过程吧。

题目代码

141，环形链表

下面我们再来了解一种双指针，我们称之为快慢指针，顾名思义一个指针速度快，一个指针速度慢。

题目描述

给定一个链表，判断链表中是否有环。pos代表环的入口，若为-1，则代表无环

如果链表中存在环，则返回 true 。否则，返回 false 。

示例1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

题目解析

题目很容易理解，让我们判断链表中是否有环，我们只需通过我们的快慢指针即可，我们试想一下，如果链表中有环的话，一个速度快的指针和一个速度慢的指针在环中运动的话，若干圈后快指针肯定可以追上慢指针的。这是一定的。

好啦，做题思路已经有了，让我们一起看一下代码的执行过程吧。

题目代码

141 ，相交链表

下面我们再来看一下另一种类型的双指针，则是遍历结束后交换起点的双指针。这个题目也是特别经典的，大家记得做一下。

题目描述

编写一个程序，找到两个单链表相交的起始节点。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

题目解析

这个题目更简单啦，我们可以这样做，我们定义两个指针，分别放到两个链表的头部，然后进行遍历，当某一指针遍历结束后，则从另一指针的起点继续遍历。这样两个指针肯定会在交点相遇的，因为他们速度相同，相同时间内路程一致，所以肯定会在交点相遇的。

我们理解了做题思路，下面我们来看一下代码的执行过程吧

题目代码

328，奇偶链表

下面我们再来看一种双指针，我称之为交替领先双指针，起名鬼才哈哈。下面我们一起来看看吧。

题目描述

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL

题目解析

题目也很容易理解就是让我们将原来奇数位的结点放一起，偶数位的结点放一起。这里需要注意哦，和结点值无关，是交换结点。下面我们分析一下做题思路。我们通过定义两个指针，一个起点为 0，一个起点为 1 .且起点为 0  的只在偶数位运行，并将偶数位连接在一起，起点为 1 的只在奇数位运行。并将奇数位连接在一起。最后再把奇数位链表的位和偶数链表的头相连就实现了，奇偶链表。是不是很简单啊！

理解了思路下面我们来看一下代码执行过程吧。

题目代码