算法技巧——双指针算法

前置知识

C 和 C++ 的数组、指针。

什么是双指针

严格的来说，双指针只能说是是算法中的一种技巧。

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

双指针问题套路

通俗的说，就是在数组遍历中，我们使用两个指针进行操作。所以双指针问题基本有以下几个细节：

1、双指针的初始位置。根据双指针的分类，有两种可能。具体看下面的介绍。

2、双指针的移动方法。根据双指针的分类，有两种可能。具体看下面的介绍。

3、遍历的结束条件。根据双指针的分类，有两种可能。具体看下面的介绍。

对撞指针

对撞指针是指在数组中，将指向最左侧的索引定义为左指针（left），最右侧的定义为右指针（right），然后从两头向中间进行数组遍历。快速排序就是典型的双指针问题。

我们假设数组名字为 nums，数组长度为 n，数组首元素对应的位置为 0。

代码细节

指针初始位置

左指针（left)一般指向数组的第一个元素。即 left = 0。

右指针（right)一般指向数组的第一个元素。即 right = n-1。

指针移动方法

左指针(left）向右边👉移动，一般每次移动一个位置，即 left++。

右指针(right）向左边👈移动，一般每次移动一个位置，即 right--。

结束条件

左指针（left）位置和右指针（right）位置逆序。

从上面的描述可知，开始的时候，right >= left。因此结束的条件就是 right < left。

伪代码

function fn(int list[], int len) {int left = 0;int right = len - 1;//遍历数组while (left <= right) {left++;// 一些条件判断 和处理... ...right--;}
}

例题

我们使用 LeetCode 881 救生艇为例，https://leetcode-cn.com/problems/boats-to-save-people/。

解题大致思路为：

1、排序。

2、初始化双指针。

3、遍历。每次都用一个最重的和一个最轻的进行配对，如果二人重量小于 Limit，则此时的最轻的上船，left++。不管最轻的是否上船，最重的都要上船，right--。并且所需船数量加一，num++。

AC 参考代码

class Solution {
public:int numRescueBoats(vector<int>& people, int limit) {sort(people.begin(), people.end());//排序int ans = 0;//答案int left = 0;//左指针int right = people.size() - 1;//右指针while (left<=right) {if (people[left]+people[right]<=limit) {left++;}right--;ans++;}return ans;}
};

快慢指针

快慢指针是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如快指针（fast）每次增长两个，慢指针（slow）每次增长一个。

一般来说，快慢指针常用于判断链表等数据结构中是否有环。比如下图所示的一个链表。

图解

下面我们用一系列图像说明，快慢指针查找环的过程。

初始位置

如下图所示，慢指针（slow）和快指针（fast）同时指向第一个元素。

`移动一次`

慢指针（slow）向后移动一个位置，快指针（fast）向后移动两个位置，如下图所示。

移动两次

慢指针（slow）向后移动一个位置，快指针（fast）向后移动两个位置，如下图所示。

移动三次

慢指针（slow）向后移动一个位置，快指针（fast）向后移动两个位置，如下图所示。我们发现慢指针（slow）和快指针（fast）重合，说明有环。

代码细节

指针初始位置

慢指针（slow）一般指向数组的第一个元素。即 slow = 0。

快指针（fast）一般指向数组的第一个元素。即 fast = 1。

指针移动方法

慢指针（slow）向右边👉移动，一般每次移动一个位置，即 slow++。

快指针（fast）向右边👉移动，一般每次移动两个个位置，即 fast += 2。

结束条件

慢指针（slow）位置和快指针（fast）位置重合；快指针（fast）达到数组的最后一个元素。

特别注意，要判断达到最后一个元素。否则会出现死循环。

伪代码

注意：伪代码只是表示一种结构。

function fn(LinkList *list, int len) {int slow = 0;int fast = 1;//遍历数组while (slow != fast) {slow++;// 一些条件判断 和处理... ...fast+=2;}
}

例题

我们使用 LeetCode 141 环形链表为例，https://leetcode-cn.com/problems/linked-list-cycle/。

解题大致思路为：

1、排序。

2、初始化双指针。

3、遍历。

AC 参考代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {ListNode *slow = head;//慢指针ListNode *fast = head;//快指针while (NULL!=fast && NULL!=fast->next && NULL!=fast->next->next) {//修改位置slow = slow->next;fast = fast->next->next;//判断有环if (slow==fast) {return true;}}//无环return false;}
};