1 双指针介绍
双指针(Two Pointers):指的是在遍历元素的过程中,不是使用单个指针进行访问,而是使用两个指针进行访问,从而达到相应的目的。
如果两个指针方向相反,则称为「对撞指针」。
如果两个指针方向相同,则称为「快慢指针」。
如果两个指针分别属于不同的数组 / 链表,则称为「分离双指针」。
2 对撞指针
2.1 对撞指针概念
对撞指针:指的是两个指针 left,right 分别指向序列第一个元素和最后一个元素,然后 left 指针不断递增,right 不断递减,直到两个指针的值相撞(即 left==right),或者满足其他要求的特殊条件为止。
[外链图片转存中…(img-JaNwjkqS-1721614459575)]
2.2 对撞指针求解步骤
1> 使用两个指针left,right。left 指向序列第一个元素,即:left=0,right 指向序列最后一个元素,即:right=len(nums)−1。
2> 在循环体中将左右指针相向移动,当满足一定条件时,将左指针右移,left+=1;当满足另外一定条件时,将右指针左移,right−=1。
3> 直到两指针相撞(即left==right),或者满足其他要求的特殊条件时,跳出循环体。
2.3 对撞指针伪代码模板
left, right = 0, len(nums) - 1
while left < right:
if 满足要求的特殊条件:
return 符合条件的值
elif 一定条件 1:
left += 1
elif 一定条件 2:
right -= 1
return 没找到 或 找到对应值
2.4 对撞指针适用范围
对撞指针一般用来解决有序数组或者字符串问题:
查找有序数组中满足某些约束条件的一组元素问题:比如二分查找、数字之和等问题。
字符串反转问题:反转字符串、回文数、颠倒二进制等问题。
下面给出具体例子来讲解如何使用对撞指针来解决问题。
3 快慢指针
3.1 快慢指针概念
快慢指针:指的是两个指针从同一侧开始遍历序列,且移动的步长一个快一个慢。移动快的指针被称为 「快指针(fast)」,移动慢的指针被称为「慢指针(slow)」。两个指针以不同速度、不同策略移动,直到快指针移动到数组尾端,或者两指针相交,或者满足其他特殊条件时为止。
[外链图片转存中…(img-8WZvC4ny-1721614459577)]
3.2 快慢指针求解步骤
1> 使用两个指针slow,fast。slow 一般指向序列第一个元素,即:slow = 0,fast 一般指向序列第n个元素,即:fast = n-1
。
2> 在循环体中将左右指针向右移动。当满足一定条件时,将慢指针右移,即 slow+=1。当满足另外一定条件时(也可能不需要满足条件),将快指针右移,即 fast+=1。
3> 到快指针移动到数组尾端(即fast==len(nums)−1),或者两指针相交,或者满足其他特殊条件时跳出循环体。
3.3 快慢指针伪代码模板
slow = 0
fast = 1
while 没有遍历完:
if 满足要求的特殊条件:
slow += 1
fast += 1
return 合适的值
3.4 快慢指针适用范围
快慢指针一般用于处理数组中的移动、删除元素问题,或者链表中的判断是否有环、长度问题。关于链表相关的双指针做法我们到链表章节再详细讲解。
下面给出具体例子来讲解如何使用快慢指针来解决问题。
4 分离指针
4.1 分离指针概念
分离双指针:两个指针分别属于不同的数组,两个指针分别在两个数组/链表中移动。
[外链图片转存中…(img-UDpuK64J-1721614459578)]
4.2 分离指针求解步骤
1> 使用两个指针left_1 ,left_2。left_1 指向第一个数组的第一个元素,即:left_1 = 0;left_2指向第二个指针的第一个数组元素,即left_2 = 0;
2> 当满足一定条件时,两个指针同时右移,即left_1 += 1、 left_2+=1;
3> 当满足另外一定条件时,将left_1指针右移,即left_1+=1;
4> 当满足其他一定条件时,将left_2指针右移,即left_2+=1;
5> 当其中一个数组遍历完时或者满足其他特殊条件时跳出循环体。
4.3 分离双指针伪代码模板
left_1 = 0
left_2 = 0
while left_1 < len(nums1) and left_2 < len(nums2):
if 一定条件 1:
left_1 += 1
left_2 += 1
elif 一定条件 2:
left_1 += 1
elif 一定条件 3:
left_2 += 1
4.4 分离双指针使用范围
分离双指针一般用于处理有序数组合并,求交集、并集问题。
下面给出具体例子来讲解如何使用分离双指针来解决问题。
5 双指针总结
双指针分为「对撞指针」、「快慢指针」、「分离双指针」。
对撞指针:两个指针方向相反。适合解决查找有序数组中满足某些约束条件的一组元素问题、字符串反转问题。
快慢指针:两个指针方向相同。适合解决数组中的移动、删除元素问题,或者链表中的判断是否有环、长度问题。
分离双指针:两个指针分别属于不同的数组 / 链表。适合解决有序数组合并,求交集、并集问题。