数组双指针系列之对撞指针
# 01. 数组双指针知识
# 1. 双指针简介
双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。如果两个指针方向相反，则称为「对撞指针」。如果两个指针方向相同，则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。
在数组的区间问题上，暴力算法的时间复杂度往往是 O(n2)。而双指针利用了区间「单调性」的性质，可以将时间复杂度降到 O(n)。
# 2. 对撞指针
对撞指针：指的是两个指针 left、right 分别指向序列第一个元素和最后一个元素，然后 left 指针不断递增，right 不断递减，直到两个指针的值相撞（即 left==right），或者满足其他要求的特殊条件为止。
# 2.1 对撞指针求解步骤
- 使用两个指针 left，right。left 指向序列第一个元素，即：left=0，right 指向序列最后一个元素，即：right=len(nums)−1。
- 在循环体中将左右指针相向移动，当满足一定条件时，将左指针右移，left+=1。当满足另外一定条件时，将右指针左移，right−=1。
- 直到两指针相撞（即 left==right），或者满足其他要求的特殊条件时，跳出循环体。
# 2.2 对撞指针伪代码模板
left, right = 0, len(nums) - 1
while left < right:
if 满足要求的特殊条件:
return 符合条件的值
elif 一定条件 1:
left += 1
elif 一定条件 2:
right -= 1
return 没找到 或 找到对应值
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 2.3 对撞指针适用范围
对撞指针一般用来解决有序数组或者字符串问题：
- 查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
- 字符串反转问题：反转字符串、回文数、颠倒二进制等问题。
下面我们根据具体例子来讲解如何使用对撞指针来解决问题。
# 2.4.2 题目大意
描述：给定一个下标从 1 开始计数、升序排列的整数数组：numbers 和一个目标值 target。
要求：从数组中找出满足相加之和等于 target 的两个数，并返回两个数在数组中下的标值。
示例：
- 示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
1
2
3
2
3
# 2.4.3 解题思路
这道题如果暴力遍历数组，从中找到相加之和等于 target 的两个数，时间复杂度为 O(n2)，可以尝试一下。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
size = len(numbers)
for i in range(size):
for j in range(i + 1, size):
if numbers[i] + numbers[j] == target:
return [i + 1, j + 1]
return [-1, -1]
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
结果不出意外的超时了。所以我们要想办法减少时间复杂度。
# 思路 1：对撞指针 (opens new window)
可以考虑使用对撞指针来减少时间复杂度。具体做法如下：
- 使用两个指针 left，right。left 指向数组第一个值最小的元素位置，right 指向数组值最大元素位置。
- 判断两个位置上的元素的和与目标值的关系。
- 如果元素和等于目标值，则返回两个元素位置。
- 如果元素和大于目标值，则让 right 左移，继续检测。
- 如果元素和小于目标值，则让 left 右移，继续检测。
- 直到 left 和 right 移动到相同位置停止检测。
- 如果最终仍没找到，则返回 [−1,−1]。
# 思路 1：代码
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left = 0
right = len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
elif total < target:
left += 1
else:
right -= 1
return [-1, -1]
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 思路 1：复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。只用到了常数空间存放若干变量。
# 2.5 验证回文串
# 2.5.1 题目链接
# 2.5.2 题目大意
描述：给定一个字符串 s。
要求：判断是否为回文串（只考虑字符串中的字母和数字字符，并且忽略字母的大小写）。
说明：
- 回文串：正着读和反着读都一样的字符串。
- 1≤s.length≤2∗105。
- s 仅由可打印的 ASCII 字符组成。
示例：
输入: "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。
输入："race a car"
输出：false
解释："raceacar" 不是回文串。
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 2.5.3 解题思路
# 思路 1：对撞指针
- 使用两个指针 left，right。left 指向字符串开始位置，right 指向字符串结束位置。
- 判断两个指针对应字符是否是字母或数字。 通过 left 右移、right 左移的方式过滤掉字母和数字以外的字符。
- 然后判断 s[start] 是否和 s[end] 相等（注意大小写）。
- 如果相等，则将 left 右移、right 左移，继续进行下一次过滤和判断。
- 如果不相等，则说明不是回文串，直接返回 False。
- 如果遇到 left==right，跳出循环，则说明该字符串是回文串，返回 True
# 思路 1：代码 (opens new window)
class Solution:
def isPalindrome(self, s: str) -> bool:
left = 0
right = len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
continue
if not s[right].isalnum():
right -= 1
continue
if s[left].lower() == s[right].lower():
left += 1
right -= 1
else:
return False
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 思路 1：复杂度分析
- 时间复杂度：O(len(s))。
- 空间复杂度：O(len(s))。
# 对撞指针题目 (opens new window)
编辑 (opens new window)