数组双指针系列之快慢指针
# 一、快慢指针
快慢指针：指的是两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢。移动快的指针被称为 「快指针（fast）」，移动慢的指针被称为「慢指针（slow）」。两个指针以不同速度、不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他特殊条件时为止。
# 1.1 快慢指针求解步骤
- 使用两个指针 slow、fast。slow 一般指向序列第一个元素，即：slow=0，fast 一般指向序列第二个元素，即：fast=1。
- 在循环体中将左右指针向右移动。当满足一定条件时，将慢指针右移，即 slow+=1。当满足另外一定条件时（也可能不需要满足条件），将快指针右移，即 fast+=1。
- 到快指针移动到数组尾端（即 fast==len(nums)−1），或者两指针相交，或者满足其他特殊条件时跳出循环体。
# 1.2 快慢指针伪代码模板
slow = 0
fast = 1
while 没有遍历完：
if 满足要求的特殊条件:
slow += 1
fast += 1
return 合适的值
1
2
3
4
5
6
7
2
3
4
5
6
7
# 1.3 快慢指针适用范围
快慢指针一般用于处理数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题。关于链表相关的双指针做法我们到链表章节再详细讲解。
下面我们根据具体例子来讲解如何使用快慢指针来解决问题
# 3.4 删除有序数组中的重复项 (opens new window)
# 3.4.1 题目链接 (opens new window)
# 3.4.2 题目大意 (opens new window)
描述：给定一个有序数组 nums。
要求：删除数组 nums 中的重复元素，使每个元素只出现一次。并输出去除重复元素之后数组的长度。
说明：
- 不能使用额外的数组空间，在原地修改数组，并在使用 O(1) 额外空间的条件下完成。
示例：
- 示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
1
2
3
2
3
- 示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
1
2
3
2
3
# 3.4.3 解题思路 (opens new window)
# 思路 1：快慢指针 (opens new window)
因为数组是有序的，那么重复的元素一定会相邻。
删除重复元素，实际上就是将不重复的元素移到数组左侧。考虑使用双指针。具体算法如下：
- 定义两个快慢指针 slow，fast。其中 slow 指向去除重复元素后的数组的末尾位置。fast 指向当前元素。
- 令 slow 在后， fast 在前。令 slow=0，fast=1。
- 比较 slow 位置上元素值和 fast 位置上元素值是否相等。
- 如果不相等，则将 slow 右移一位，将 fast 指向位置的元素复制到 slow 位置上。
- 将 fast 右移 1 位。
- 重复上述 3∼4 步，直到 fast 等于数组长度。
- 返回 slow+1 即为新数组长度。
# 思路 1：代码
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) <= 1:
return len(nums)
slow, fast = 0, 1
while (fast < len(nums)):
if nums[slow] != nums[fast]:
slow += 1
nums[slow] = nums[fast]
fast += 1
return slow + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 思路 1：复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
# 快慢指针题目 (opens new window)
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0026 | 删除有序数组中的重复项 (opens new window) | Python (opens new window) | 数组、双指针 | 简单 |
| 0080 | 删除有序数组中的重复项 II (opens new window) | Python (opens new window) | 数组、双指针 | 中等 |
| 0027 | 移除元素 (opens new window) | Python (opens new window) | 数组、双指针 | 简单 |
| 0283 | 移动零 (opens new window) | Python (opens new window) | 数组、双指针 | 简单 |
| 0845 | 数组中的最长山脉 (opens new window) | Python (opens new window) | 数组、双指针、动态规划、枚举 | 中等 |
| 0088 | 合并两个有序数组 (opens new window) | Python (opens new window) | 数组、双指针、排序 | 简单 |
| 0719 | 找出第 K 小的数对距离 (opens new window) | Python (opens new window) | 数组、双指针、二分查找、排序 | 困难 |
| 0334 | 递增的三元子序列 (opens new window) | Python (opens new window) | 贪心、数组 | 中等 |
| 0978 | 最长湍流子数组 (opens new window) | Python (opens new window) | 数组、动态规划、滑动窗口 | 中等 |
| 剑指 Offer 21 | 调整数组顺序使奇数位于偶数前面 (opens new window) | Python (opens new window) | 数组、双指针、排序 | 简单 |
编辑 (opens new window)