数组双指针系列之分离双指针
# 一. 分离双指针
分离双指针：两个指针分别属于不同的数组，两个指针分别在两个数组中移动。
# 1.1 分离双指针求解步骤
- 使用两个指针 left1、left2。left1 指向第一个数组的第一个元素，即：left1=0，left2 指向第二个数组的第一个元素，即：left2=0。
- 当满足一定条件时，两个指针同时右移，即 left1+=1、left2+=1。
- 当满足另外一定条件时，将 left1 指针右移，即 left1+=1。
- 当满足其他一定条件时，将 left2 指针右移，即 left2+=1。
- 当其中一个数组遍历完时或者满足其他特殊条件时跳出循环体。
# 1.2 分离双指针伪代码模板
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
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 1.3 分离双指针使用范围
分离双指针一般用于处理有序数组合并，求交集、并集问题。
下面我们根据具体例子来讲解如何使用分离双指针来解决问题。
# 1.4 两个数组的交集]
# 1.4.1 题目链接
# 1.4.2 题目大意
描述：给定两个数组 nums1 和 nums2。
要求：返回两个数组的交集。重复元素只计算一次。
说明：
- 1≤nums1.length,nums2.length≤1000。
- 0≤nums1[i],nums2[i]≤1000。
示例：
- 示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
1
2
3
2
3
- 示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
1
2
3
2
3
# 1.4.3 解题思路
# 思路 1：分离双指针
- 对数组 nums1、nums2 先排序。
- 使用两个指针 left1、left2。left1 指向第一个数组的第一个元素，即：left1=0，left2 指向第二个数组的第一个元素，即：left2=0。
- 如果 nums1[left1]==nums2[left2]，则将其加入答案数组（注意去重），并将 left1 和 left2 右移。
- 如果 nums1[left1]<nums2[left2]，则将 left1 右移。
- 如果 nums1[left1]>nums2[left2]，则将 left2 右移。
- 最后返回答案数组。
# 思路 1：代码
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
left_1 = 0
left_2 = 0
res = []
while left_1 < len(nums1) and left_2 < len(nums2):
if nums1[left_1] == nums2[left_2]:
if nums1[left_1] not in res:
res.append(nums1[left_1])
left_1 += 1
left_2 += 1
elif nums1[left_1] < nums2[left_2]:
left_1 += 1
elif nums1[left_1] > nums2[left_2]:
left_2 += 1
return res
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(n)。
- 空间复杂度：O(1)。
# 1.5. 双指针总结
双指针分为「对撞指针」、「快慢指针」、「分离双指针」。
- 对撞指针：两个指针方向相反。适合解决查找有序数组中满足某些约束条件的一组元素问题、字符串反转问题。
- 快慢指针：两个指针方向相同。适合解决数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题。
- 分离双指针：两个指针分别属于不同的数组 / 链表。适合解决有序数组合并，求交集、并集问题。
# 分离双指针题目 (opens new window)
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0350 | 两个数组的交集 II (opens new window) | Python (opens new window) | 数组、哈希表、双指针、二分查找、排序 | 简单 |
| 0925 | 长按键入 (opens new window) | Python (opens new window) | 双指针、字符串 | 简单 |
| 0844 | 比较含退格的字符串 (opens new window) | Python (opens new window) | 栈、双指针、字符串、模拟 | 简单 |
| 1229 | 安排会议日程 (opens new window) | Python (opens new window) | 数组、双指针、排序 | 中等 |
| 0415 | 字符串相加 (opens new window) | Python (opens new window) | 数学、字符串、模拟 | 简单 |
| 0392 | 判断子序列 (opens new window) | Python (opens new window) | 双指针、字符串、动态规划 | 简单 |
编辑 (opens new window)