算法:双指针
- 双指针
- 快慢指针
- 对撞指针
- 总结
双指针
LeetCode 283.移动零
以上题目要求我们把所有0
移动到数组的末尾,也就是说,我们要把数组转化为以下状态:
[ 非0区域 ] [ 0区域 ]
像这种把一个数组划分为多个区域的题型,就是数组划分。而数组划分非常适合使用双指针算法。
对于这道题,我们可以用两个指针,对数组进行动态的区域划分。
其中dest
指针维护一段区域,表示非0区域
,cur
指针与dest
之间的区域是0区域
。而cur
后面的区域是待处理区域
。
也就是我们的数组被划分为了以下情况:
[ 非0区域 ]
[ 0区域 ]
[ 待处理区域 ]
当我们的cur
移动后,对于一个新的数据,就要根据条件来决定把它放到哪一个区域去。当cur
指针走到末尾,数组就被处理为了:
[ 非0区域 ]
[ 0区域 ]
也就是题目要求的样子了。
对于本题而言,如果新插入的数据是0
,那就放到cur
维护的区域里面,此时直接cur++
即可;如果新插入的数据是非0
,那么就放到dest
的末尾,为了保证dest
不会覆盖掉cur
原本维护的0
,因此要进行一个交换操作。
代码如下:
class Solution
{
public:void moveZeroes(vector<int>& nums) {int dest = -1;int cur = 0;int sz = nums.size();while (cur < sz){if (nums[cur])swap(nums[++dest], nums[cur]);cur++;}}
};
LeetCode 75.颜色分类
这一题也是一个区域划分问题,根据上一题的思路,我们可以把数组划分为以下状态:
[ 0区域 ]
[ 1区域 ]
[ 2区域 ]
相比于上一题,这次我们要划分出三个区域来,毫无疑问就需要更多的指针来维护区域,大致可以划分为:
[ 0区域 ]
[ 1区域 ]
[ 待处理 ]
[ 2区域 ]
我们让维护0区域
的指针left
向右拓展,维护2区域
的指针right
向左拓展,以及利用cur
指针向右遍历数组:
上图中,left
指针左侧维护了一段0区域
,left
与cur
之间维护了一段1区域
,cur
与right
之间是待处理区域,right
右侧是2区域
。当cur
往后遍历,如果遇到一个新的数据,就要决定把它放到哪一个区域去:
- 遇到
0
,就交换++left
与cur
的值,把0
放到left
后面一位,拓展left
指针维护的区域- 遇到
1
,就直接++cur
,把1
放到cur
与left
之间- 遇到
2
,就交换--right
与cur
的值,把2
放到right
的前面一位,拓展right
维护的区域
要注意的是,当把0
交给left
后,cur++
;但是当把2
交给right
后,cur
不能移动。因为left
后面的一位数一定是符合cur
范围要求的,也就是区间(left, cur]
之间的数据被交换到了cur
的位置,此时不用判断被交换过来的数据。而right
的前面一位数据是不确定的,也就是把区间(cur, right)
之间的数据,交换给了cur
。而(cur, right)
之间的数据是待处理的不确定数据,因此还需要额外判断一次。比如上图中,right
的前一位数据就是0
,交换后状态如下:
可以看到,cur
得到的数据是0
,应该被放到left
维护的区域去。
总代码如下:
class Solution
{
public:void sortColors(vector<int>& nums){int left = -1;int right = nums.size();int cur = 0;while (cur < right){if (nums[cur] == 0)swap(nums[++left], nums[cur++]);else if (nums[cur] == 2)swap(nums[--right], nums[cur]);//交换后不能cur++,进入下一轮循环在判断一次cur的值elsecur++;}}
};
快慢指针
LeetCode 202.快乐数
该题的意思是,每个数字的下一个数字是该数字所有位的平方和,比如 19 的下一位数字就是 1 2 + 9 2 = 82 1^{2} + 9^{2} = 82 12+92=82。一直以这个规则操作下去,会出现两种情况:
- 最后该数字变为1,那么该数字是快乐数
- 该数字陷入死循环,那么该数字不是快乐数
- 比如
19 -> 82 -> 68 -> 100 -> 1
,最后19
变成了1
,所以19
是一个快乐数 - 比如
2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4
,可以发现其陷入了一个死循环,从4
开始又以4
结束,那么2
就不是一个快乐数
这题的难点不在于如何计算下一位快乐数字,而在于如何判断一个数字陷入了死循环。
对于这种循环问题,就可以使用快慢指针。
快慢指针规则如下:
- 定义两个变量
fast
与slow
fast
走2
步,slow
走一步- 如果
fast
走到终点,说明没有循环- 如果
fast
与slow
相遇,说明陷入了循环
一开始fast
和slow
都在起点:
fast
走两步,slow
走一步:
由于这是一个循环结构,当fast
进入第二圈循环,slow
还没有走完第一圈:
这个时候,由于slow
的速度为1
,fast
的速度为2
,那么每次行动fast
与slow
的距离就会缩短1
,最后fast
一定可以遇到slow
:
此时两者相遇,说明这是一个循环结构。
因此代码逻辑如下:
- 定义两个变量,
fast
和slow
,fast
走两步,slow
走一步- 如果
fast
变成1,那么该数字是快乐数,返回true
- 如果
fast
与slow
相遇,那么有循环结构,该数字不是快乐数,返回false
代码如下:
class Solution
{
public:int getNextNum(int n) //到下一个数字的函数{int num = 0;while (n){int tmp = n % 10;num += tmp * tmp;n /= 10;}return num;}bool isHappy(int n) {int fast = n;int slow = n;while (fast != 1){fast = getNextNum(getNextNum(fast));//fast走两步slow = getNextNum(slow);//slow走一步if (fast == slow && fast != 1)//两者相遇,有循环return false;} return true;//到这里说明fast = 1,是快乐数}
};
其中有一个注意点,就是条件fast == slow && fast != 1
,这里一种情况就是fast
虽然和slow
相等,但是两者都为1
,此时是快乐数。
比如数字10
,10 -> 1 -> 1
,slow
走第一步就是1
了,fast
走两步也是1
,此时两者相等。
LeetCode 141.环形链表
本题要求判断一个链表中有没有环结构,那就是一个循环问题,要使用快慢指针。
我们刚刚已经讲解过快慢指针了,现在我们直接说明代码逻辑:
- 定义两个指针
fast
和slow
,fast
走两步,slow
走一步- 如果
fast
为nullptr
,说明链表无环,返回true
- 如果
fast
与slow
相遇,说明有环,返回false
代码如下:
class Solution {
public:bool hasCycle(ListNode* head){ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (fast == slow)return true;}return false;}
};
注意事项:
- 进入循环时,因为
fast
要走两步,因此要判断fast->next
是不是空指针,否则fast->next-->next
就是访问空指针行为
LeetCode 142.环形链表II
这道题要求我们求出环形链表的环入口,这就麻烦了,通过之前的fast
与slow
的快慢指针追击问题,我们已经可以判断是否存在环结构了,那么我们要如何求环入口呢?
看到以下示意图:
现在slow
和fast
刚好相遇,参数含义如下:
L
:从起点到环入口的距离
C
:环周长
X
:相遇点和环入口的距离
由于fast
的速度是slow
的两倍,当slow
走的距离是L + X
,因此此时fast
走了2(L + X)
的距离。
又由于fast
一定经过了起点到入口的L
距离,因此此时fast
在环中走了2(L + X) - L = L + 2X
的距离。
假设fast
已经在环中转了n
圈,因此此时fast
在环中走了nC + X
的距离
那么可以列出公式:
n C + X = L + 2 X nC + X = L + 2X nC+X=L+2X
变形得到:
n C − X = L \mathbf{{\color{Red} nC - X = L} } nC−X=L
这个公式具有重大意义,L
代表起点到入口的距离,nC
代表n
个环周长,X
代表当前相遇点与入口的距离。
nC -X
整体可以看成(n - 1)C + (C - X)
,而C - X
就代表相遇点开始与环入口的优弧的长度。
此时如果让一个指针A
从起点开始走L
的距离所用的时间,和让一个指针B
从相遇点开始走n - 1
圈外加一个C - X
的距离所用的时间是一致的。由于相遇点与环入口距离已经是X
了,那么指针B
最后刚好会走到环入口。而指针A
从入口开始走L
到达的地方也是环入口,因此两者相遇!
通过这个公式可知:让一个指针从起点开始走,一个指针从相遇点开始走,两者会在环入口相遇!
因此我们的代码逻辑如下:
- 定义两个指针
fast
和slow
,fast
走两步,slow
走一步- 如果
fast
为nullptr
,说明链表无环,返回nullptr
- 如果
fast
与slow
相遇,说明有环,开始找环入口
- 在相遇点定义一个指针
B
,也就是B = slow
;在起点定义一个指针A
,也就是A = head
- 两个指针各自行动,速度一致,最后
A
与B
相遇的地方就是环入口- 返回
A
或B
代码如下:
class Solution
{
public:ListNode* detectCycle(ListNode* head){ListNode* fast = head;ListNode* slow = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (slow == fast) // 有环,开始找入口{ListNode* A = head;ListNode* B = slow;while (A != B)//A与B相遇点,就是环入口{A = A->next;B = B->next;}return A;}}return nullptr; //没有环,返回空指针}
};
对撞指针
LCR 179.查找总价格为目标值的两个商品
这道题给了一个升序数组,要求我们求出数组中任意两个值的和刚好为target
。
该数组有一个特点:有序数组。像这种在一个有序区间中查找两个元素,计算得到固定值的题型,就可以使用对撞指针。
如果我们直接暴力解法的话,那就是枚举所有两两一对的元素组,直到某一对刚好和为target
,时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)。
假设现在的数组为[8, 21, 27, 34, 52]
,target = 61
:
因为数组具有单调性,我们可以一开始就枚举最左侧和左右侧的两个元素:
当前8 + 52 = 60
比61
小,说明我们需要一个更大的值来增大当前总和。那么由于数组升序,我们只需要left++
即可:
当前21 + 52 = 73
比61
大,说明我们需要一个更小的值来缩小当前总和。那么由于数组升序,我们只需要right--
即可:
当前21 + 34 = 55
比61
小,说明我们需要一个更大的值来增大当前总和。那么由于数组升序,我们只需要left++
即可:
当前27 + 34 = 61
,我们就找到了目标值,返回left
与right
下标即可。
正是由于数组单调性,我们可以通过比大小来进行指针的调整,来决定当前总值要变大还是变小,如果最后left
与right
相遇了,说明不存在这样的和。
为什么可以这样优化呢?看到这个例子:
对于34
而言,其要去枚举除了自己以外的所有值,但是当前21 + 34 = 55
比61
小,如果把21
改为8
,那只总和只会更小,因此我们只需要再枚举比21
大的值即可。也就是通过单调性,免去了很多不必要的枚举行为。
代码如下:
class Solution
{
public:vector<int> twoSum(vector<int>& price, int target){int left = 0;int right = price.size() - 1;while (left < right){if (price[left] + price[right] > target) //和比target大,right--right--;else if (price[left] + price[right] < target) //和比target小,left++left++;elsereturn { price[left], price[right] };}return { 0, 0 };}
};
LeetCode 11.盛水最多的容器
本题要求存储的最大水量,其实也就是两个下标之间的距离right - left
与min(height[left], height[right])
的乘积。
如果暴力枚举,那么就是枚举出每一对下标,然后求出最大面积,时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)。
本题也可以使用双指针的算法,水量的值与right - left
与min(height[left], height[right])
两个变量正相关,如果我们利用两个指针向内枚举,那么right - left
这个值是一直在减小的,也就是有一项有单调性。
对于这种,如果利用对撞指针下标向内枚举,对组成结果的某一项变量的影响是单调的,就可以考虑对撞指针。
假设我们已经在边界上定义好了left
与right
指针:
第一个问题就是,应该以什么规则进行向内移动指针?
移动的过程中,水的宽度的一直递减的,那么我们就要尽可能找到height
高的元素,来拔高水量。
比如说当前的两个高度为3
和7
,由于水的高度取决于较低的那个元素,因此高度为7
的指针无论怎么向内移动,水高度都不会超过3
,而这个过程中宽度又是单调递减的,因此right
指针向内移动,所有的结果都小于当前的水量。
比如这个情况:
虽然right
向内移动,找到了比7
更大的元素,但是由于此时水高度取决于3
,而且宽度还变小了,最后总水量没有变大。
因此每次都把比元素值较小的那个指针向内移动
代码如下:
class Solution
{
public:int maxArea(vector<int>& height){int left = 0;int right = height.size() - 1;int ret = -1;while (left <= right){int w = right - left;//宽度int h = min(height[left], height[right]);//高度ret = max(ret, w * h);//更新最大水量//每次都让较小的元素向内枚举if (height[left] > height[right])right--;elseleft++;}return ret;}
};
总结
双指针
- 数组划分使用双指针算法。
一般处理为[A区域][B区域]...[待处理]
这样的格式,当新元素符合哪一个区域特性,就放到哪一个区域中。
快慢指针
- 循环问题,利用快慢指针来判断是否有循环。
相遇就是有环,如果fast
走到结尾就是无环。
如果要找循环开始节点,一个指针从头开始走,一个指针从相遇点开始走,最后会在环入口相遇。
对撞指针
-
在一个有序区间中查找两个元素,计算得到固定值的题型,使用对撞指针。
-
如果利用对撞指针下标向内枚举,对组成结果的影响是单调的,就可以考虑对撞指针。
对撞指针的特点在于利用单调性减小搜索范围。