对撞指针

基本概念

对撞指针：即用两个指针left 和 right,分别指向序列的首尾，left向右，right向左移动，直到两指针相遇($left==right$)或满足特定条件

求解步骤

1. 初始化：left=0,right=len(nums)-1
2. 循环移动指针：根据特定条件，移动指针
3. 结束循环：两指针相遇或满足特定条件

通用模板：

#1. 初始化：left=0,right=len(nums)-1
left,right=0,len(nums)-1
#2. 循环移动指针：根据特定条件，移动指针
while left<right:
	if 满足条件：
		return 
	elif 满足条件1：
		left+=1
	elif 满足条件2：
		right-=1
return 没找到

应用场景：

对撞指针常用于有序数组或字符串，典型应用包括：

• 查找有序数组中特定元素组合，如二分查找、两数之和等。

• 字符串或数组反转，如反转字符串、判断回文、颠倒二进制等。

• 344.反转字符串

• 345.反转字符串中的元音字母

• 15.三数之和

• 125.验证回文串