警告
本文最后更新于 2023-01-16，文中内容可能已过时。
理解对撞指针算法
对撞指针技巧指的是：有两个指针位于数组（通常有序）的头和尾，通过不断的向对方移动来解决问题。
其核心思想是利用额外的指针来避免重复扫描数组，以减少工作量。
这里直接给出解体模板：
-
对数组排序（可选，具体以题目为准）
-
两个指针位于数组头和尾。
-
两个指针分别向对方移动，并且在碰撞时结束。
下面我们通过 LeetCode 第 167 题（两数之和）来练习这套模板：
小试牛刀：LeetCode167题解
题干简述
给定：有序数组、常数target。
现要求：从数组中找出两个数，这两数的要求是二者之和等于target。
详情请看：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
解题思路
该题用暴力法可以解决，但是两层for循环势必会浪费很多工作量。
这里我们尝试用对撞指针法解决这个问题：
-
利用两个指针从数组中取数。
-
如果两数之和 > target，则 j 左移，否则 i 右移。
-
按照上面的模式扫描数组，若两数之和 = target，则这一对数字为结果。
显而易见，最差的情况是扫描整个数组，时间复杂度为O(N)，对比暴力法O(N2)的时间复杂度，我们仅多创造了一个指针，就获得了时间复杂度的巨大提升。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i = 0
j = len(numbers)-1
while 1:
sum = numbers[i] + numbers[j]
if sum < target:
i = i+1
elif sum > target:
j = j-1
else:
break
return i+1,j+1
|
趁热打铁：LeetCode15题解
题干简述
给定：整数数组。
要求：尽可能多的找出数组中的三个数，这三个数的要求是三者之和等于 0。
详情请看：https://leetcode.cn/problems/3sum/
解题思路
-
对数组排序。
-
确定第一个数。
-
用对撞指针算法将另外两个数找出来。
-
因为题目要求：结果不能重复，所以还需要留意下去重。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
target = 0
if (len(nums) < 3):
return result
nums.sort()
for i in range(len(nums)):
j = i + 1
k = len(nums) - 1
while j < k:
sum = nums[i] + nums[j] + nums[k]
if (sum < target):
j += 1
elif (sum > target):
k -= 1
else:
sumResult = [nums[i], nums[j], nums[k]]
if sumResult not in result:
result.append(sumResult)
j += 1
return result
|
乘胜追击：LeetCode18题解
题干简述
跟 LeetCode 13 题差不多，只不过变成了 4 个数。
详情请看：https://leetcode.cn/problems/4sum/
解题思路
-
对数组排序。
-
确定第一个数。
-
确定第二个数。
-
用对撞指针算法将另外两个数找出来。
-
因为题目要求：结果不能重复，所以还需要留意下去重。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
result = []
if (len(nums) < 4):
return result
nums.sort()
for i in range(0, len(nums)-3):
for j in range(i+1, len(nums)-2):
l = j + 1
r = len(nums)-1
while l < r:
sum = nums[i]+nums[j]+nums[l]+nums[r]
if (sum > target):
r -= 1
elif (sum < target):
l += 1
else:
subRes = [nums[i], nums[j], nums[l], nums[r]]
if subRes not in result:
result.append(subRes)
l += 1
return result
|
总结:
经过上面的训练我们可以得出一个结论：利用对撞指针算法可以以较低的时间、空间复杂度来解决「两数之和」这种问题，对于三数之和、四数之和无非是基于二数之和衍生出来的题目。我们可以从代码中总结出对撞指针算法的模板：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
l = j + 1
r = len(nums)-1
while l < r:
sum = nums[i]+nums[j]+nums[l]+nums[r]
if (sum > target):
r -= 1
elif (sum < target):
l += 1
else:
subRes = [nums[i], nums[j], nums[l], nums[r]]
if subRes not in result:
result.append(subRes)
l += 1
|
除了 「“X” 数之和」 这种题目，对撞指针算法还可以用来解决下述题目：
- LeetCode 7 整数反转
- LeetCode 9 回文数
- LeetCode 11 盛最多水的容器
- LeetCode 27 移除元素
- LeetCode 125 验证回文串
- LeetCode 344 反转字符串
- LeetCode 345 反转字符串中的元音字母
因为时间问题我目前并没有一一验证上述题目是否能用对撞指针算数解出，感兴趣的朋友可以去试试～
所有题解我上传到了 Github：https://github.com/kaolengmian7/algorithm-python
特别鸣谢：山景城一姐的视频给予我的灵感，下面给出她 Youtube 视频：
支付宝
微信