【算法详解】双指针

双指针

常见的双指针有两种形式，一种是对撞指针，一种是左右指针。

1. 双指针简介

双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。如果两个指针方向相反，则称为「对撞指针」。如果两个指针方向相同，则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。

在数组的区间问题上，暴力算法的时间复杂度往往是 $O(n^2)$。而双指针利用了区间「单调性」的性质，可以将时间复杂度降到 $O(n)$。

2. 对撞指针

对撞指针：指的是两个指针 left、right 分别指向序列第一个元素和最后一个元素，然后 left 指针不断递增，right 不断递减，直到两个指针的值相撞（即 left == right），或者满足其他要求的特殊条件为止。

对撞指针一般用于顺序结构中，也称为左右指针。

• 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
• 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
  • left == right（两个指针指向同一个位置）
  • 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 对撞指针适用范围

对撞指针一般用来解决有序数组或者字符串问题：

• 查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
• 字符串反转问题：反转字符串、回文数、颠倒二进制等问题。

下面我们根据具体例子来讲解如何使用对撞指针来解决问题。

盛最多水的容器

题目链接

11. 盛最多水的容器 - 力扣（LeetCode）

题目大意

给定 n 个非负整数 a1, a2, ..., an，每个数代表坐标中的一个点 (i, ai)。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

解题思路

思路 1：对撞指针

设两个指针 left、right 分别指向容器的左右两个端点，此时容器的容积为：

v = (right - left) * min( height[right], height[left])

容器的左边界为 height[left]，右边界为 height[right]。

为了方便叙述，我们假设「左边边界」小于「右边边界」。

如果此时我们固定一个边界，改变另一个边界，水的容积会有如下变化形式：

• 容器的宽度一定变小。
• 由于左边界较小，决定了水的高度。如果改变左边界，新的水面高度不确定，但是一定不会超过右边的柱子高度，因此容器的容积可能会增大。
• 如果改变右边界，无论右边界移动到哪里，新的水面的高度一定不会超过左边界，也就是不会超过现在的水面高度，但是由于容器的宽度减小，因此容器的容积一定会变小。

由此可见，左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界，继续去判断下一个左右边界。

当我们不断重复上述过程，每次都可以舍去大量不必要的枚举过程，直到 left 与 right 相遇。期间产生的所有的容积里面的最大值，就是最终答案

解题代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, res = 0;
        while(left < right) {
            if(height[left]<height[right])
            {
               res=max(res,height[left]*(right-left));
                left++;
            }
            else {
                res=max(res,height[right]*(right-left));
                right--;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.快慢指针

快慢指针：指的是两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢。移动快的指针被称为 「快指针（fast）」，移动慢的指针被称为「慢指针（slow）」。两个指针以不同速度、不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他特殊条件时为止。

快慢指针，又称为乌龟赛跑算法，其基本思想是使用两个移动速度不同的指针在数组或链表等序列结构上移动。

快慢指针是指两个指针在链表上移动的速度不同，常用于解决环形链表相关的问题。快指针每次移动两步，慢指针每次移动一步，因此快指针会比慢指针快一倍。快慢指针的经典应用包括：

• 判断一个链表是否存在环。
• 找到链表的中间节点。
• 判断链表是否为回文结构。

3.1 快慢指针求解步骤

1. 使用两个指针 slow、fast。slow 一般指向序列第一个元素，即：slow = 0，fast 一般指向序列第二个元素，即：fast = 1。
2. 在循环体中将左右指针向右移动。当满足一定条件时，将慢指针右移，即 slow += 1。当满足另外一定条件时（也可能不需要满足条件），将快指针右移，即 fast += 1。
3. 到快指针移动到数组尾端（即 fast == len(nums) - 1），或者两指针相交，或者满足其他特殊条件时跳出循环体。

3.2 快慢指针伪代码模板

slow = 0
fast = 1
while 没有遍历完：
    if 满足要求的特殊条件:
        slow += 1
    fast += 1
return 合适的值
1
2
3
4
5
6
7

3.3 快慢指针适用范围

快慢指针一般用于处理数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题。关于链表相关的双指针做法我们到链表章节再详细讲解。

下面我们根据具体例子来讲解如何使用快慢指针来解决问题。

删除有序数组中的重复项

题目链接

26. 删除有序数组中的重复项 - 力扣（LeetCode）

题目大意

描述：给定一个有序数组 nums。

要求：删除数组 nums 中的重复元素，使每个元素只出现一次。并输出去除重复元素之后数组的长度。

说明：

• 不能使用额外的数组空间，在原地修改数组，并在使用 $O(1)$ 额外空间的条件下完成。

示例：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 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
4
5
6
7
8

解题思路

思路 1：快慢指针

因为数组是有序的，那么重复的元素一定会相邻。

删除重复元素，实际上就是将不重复的元素移到数组左侧。考虑使用双指针。具体算法如下：

• 定义两个快慢指针 slow，fast。其中 slow 指向去除重复元素后的数组的末尾位置。fast 指向当前元素。
• 令 slow 在后， fast 在前。令 slow = 0，fast = 1。
• 比较 slow 位置上元素值和 fast 位置上元素值是否相等。
  • 如果不相等，则将 slow 后移一位，将 fast 指向位置的元素复制到 slow 位置上。
• 将 fast 右移 1 位。
• 重复上述步骤，直到 fast 等于数组长度。
• 返回 slow + 1 即为新数组长度。

解题代码

int removeDuplicates(vector<int>& nums) {
    if(nums.empty()) return 0;
    int p = 0;
    int q = 1;
    while(q < nums.size()){
        if(nums[p] != nums[q]){
            nums[p + 1] = nums[q];
            p++;
        }
        q++;
    }
    return p + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13