算法模板-双指针

Bertha 。 2022-09-15 15:48 205阅读 0赞

## 简介 ##

在很多数组问题中，双指针是一个反复被提及的解法。所谓双指针，指的是在对象遍历的过程中，并非单个指针进行访问，而是使用两个同向（快慢指针）或者反向（对撞指针）来进行扫描，从而达到相应的目的。也有时候，为了处理多数组问题使用多个指针，称为分离指针。双指针利用了数组是顺序存储这一特性，在某些情况下可以简化运算并表现得很优雅。

## 快慢指针 ##

快慢指针指的是两个指针从数组同一侧开始向另一侧遍历（即**同向**），将这两个指针分别定义为**快指针（fast）和慢指针（slow）**，两个指针以不同的策略移动，直到两个指针的位置重合（或者其他终止条件），比较典型的例子是快指针每次移动两步，慢指针每次移动一步。

快慢指针的经典例题为[环形链表][Link 1]，题目和示例如下。

给定一个链表，判断链表中是否有环。如果链表中存在环，则返回 true 。 否则，返回 false 。

**示例**

![在这里插入图片描述][0e8845418582439f8dd7b57d2990da3a.png_pic_center]

输入：head = [3,2,0,-4], pos = 1
    输出：true
    解释：链表中有一个环，其尾部连接到第二个节点。

这道题双指针的思路来源于Floyd 判圈算法（也叫龟兔赛跑算法），简述如下。

> 若是两个人从同一地点起跑，一个运动员速度快一个速度慢。那么当跑道有环的时候，跑得快的一定会比跑得慢的先进入环内并在环内移动，等到跑的慢的进入环里面的时候，由于跑的快的那个人速度快，他一定会在某个时刻与跑的慢的相遇，即套了跑的慢的若干圈。若跑道没有环，显然两人永远不会相遇。

借用上面的思路，我们可以定义一快一慢两个指针，慢指针每次移动一步，快指针每次移动两步。一开始这两个指针都指向head，如果移动过程中快指针反过来追上了慢指针，那么一定存在环形链表，否则快的指针会到达链表尾部（链表无环）。

上述解法的Python代码如下。

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            p1, p2 = head, head
            while p2 != None and p2.next != None:
                p1 = p1.next
                p2 = p2.next.next
                if p1 == p2:
                    return True
            return False

## 对撞指针 ##

对撞指针指的是两个指针从数组的不同侧向另一侧移动（即**反向**），其中左侧的称为**左指针（left**），右侧的称为**右指针（right）**。需要注意的是，**对撞指针适用于有序数组，当你遇到题意为有序数组时应当首先考虑对撞指针。**

对撞指针的经典例题为[两数之和 II - 输入有序数组][II -]，题目和示例如下。

给定一个已按照 非递减顺序排列 的整数数组 `numbers` ，请你从数组中找出两个数满足相加之和等于目标数`target` 。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。`numbers` 的下标 从 1 开始计数 ，所以答案数组应当满足 `1 <= answer[0] < answer[1] <= numbers.length`。你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

**示例**

输入：numbers = [2,7,11,15], target = 9
    输出：[1,2]
    解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。**由于题目说明答案唯一，因此一定可以找到唯一解。**

上述解法的Python代码如下。

class Solution:
        def twoSum(self, numbers: List[int], target: int) -> List[int]:
            left = 0
            right = len(numbers) - 1
            while left < right:
                if numbers[left] + numbers[right] < target:
                    left += 1
                elif numbers[left] + numbers[right] > target:
                    right -= 1
                else:
                    return [left+1, right+1]

## 分离指针 ##

分离指针在两个不同的数组中，使用两个不同的指针来进行遍历。分离指针适用于双数组或者多数组问题。

分离指针的经典例题为[两个数组的交集][Link 2]，题目和示例如下。

给定两个数组，编写一个函数来计算它们的交集。

**示例**

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出：[9,4]

这道题的双指针解法为将两个数组排序，然后两个指针遍历两个数组。具体来看，两个指针分别指向两个数组的头部，每次比较两个指针指向位置的数字。若不等，则较小数字位置的指针右移；若相等且该数字不等于上次加入交集的值pre，则将该数字添加到交集中并更新pre，两个指针都右移。当其中一个指针到达数组末端，停止遍历。

上述解法的代码如下。

class Solution:
        def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
            nums1, nums2 = sorted(nums1), sorted(nums2)
            m, n = len(nums1), len(nums2)
            intersection = []
            i, j = 0, 0
            while i < m and j < n:
                num1, num2 = nums1[i], nums2[j]
                if num1 == num2:
                    if not intersection or num1 != intersection[-1]:
                        intersection.append(num1)
                    i += 1
                    j += 1
                elif num1 < num2:
                    i += 1
                else:
                    j += 1
            return intersection

## 练习题 ##

对双指针感兴趣的可以访问力扣上的[双指针专题][Link 3]，上一节以[141题][Link 1]和[167题][Link 1]为例简单理解了快慢指针和对撞指针。

*  快慢指针的题还有[26. 删除有序数组中的重复项][26.]、[27. 移除元素][27.]、[283. 移动零][283.]等。
 *  对撞指针的题还有[15. 三数之和][15.]、[16. 最接近的三数之和][16.]、[881. 救生艇][881.]等。
 *  分离指针的题还有[88. 合并两个有序数组][88.]、[350. 两个数组的交集 II][350. _ II]等。

## 补充说明 ##

遇到数组的问题，应当首先想到使用**双指针**进行解题，因为两个指针的同时遍历策略会大大减少时间和空间复杂度。

[Link 1]: https://leetcode-cn.com/problems/linked-list-cycle/
[0e8845418582439f8dd7b57d2990da3a.png_pic_center]: /images/20220828/4297864faf75461c9f7bf122b9a32ad5.png
[II -]: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
[Link 2]: https://leetcode-cn.com/problems/intersection-of-two-arrays/
[Link 3]: https://leetcode-cn.com/tag/two-pointers/problemset/
[26.]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
[27.]: https://leetcode-cn.com/problems/remove-element/
[283.]: https://leetcode-cn.com/problems/move-zeroes/
[15.]: https://leetcode-cn.com/problems/3sum/
[16.]: https://leetcode-cn.com/problems/3sum-closest/
[881.]: https://leetcode-cn.com/problems/boats-to-save-people/
[88.]: https://leetcode-cn.com/problems/merge-sorted-array/
[350. _ II]: https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/