以下代码环境为 VS2022 C++ 或 力扣OJ 或 牛客网OJ。

一、双指针算法介绍

“ 双指针 ” 中的 “ 指针 ” 并不是指使用 指针 类型，而是像指针一样能够找到数据集合中的指定元素。

双指针算法更严谨点是一种思想：使用两个 “ 指针 ” ，在一个特定的移动规则中，基于一种算法达到优化时间复杂度的目的。

则它的有效使用条件：

1. 移动规则：一个有穷计算的移动规则，并且必须具有单调性。

2. 算法：使用的算法是可行且能优化时间复杂度的。

什么是单调性？

从广义上说，一个事件能用数学描述则是有规律的，而这个规律不会重复，就具有单调性。

从计算机的角度来说，一个算法不是回溯的，就具有单调性。

双指针算法的常用方法可大致分类为：

1. 交换与覆盖

2. 快慢与对撞

接下来我们在实际的题目中去初步实现与讲解双指针算法的使用。

二、常用方法讲解

交换、覆盖、快慢、对撞方法实际上是单调性的子集，由于这四种在双指针中比较经典，值得单独拿出来讲解。

如果要解释他们所有方法的关系，用图比较明显：

交换

交换指的是双指针两个条件中的算法方面，“ 指针 ” 移动规则未定。

力扣：283.移动零

力扣：283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:
输入: nums = [0]
输出: [0]

原题详细信息请参考：力扣：283. 移动零

class Solution {
public:void moveZeroes(vector<int>& nums) {int i = 0;                          // 检测指针int j = 0;                          // 交换指针while (i < nums.size()){if (nums[i] != 0)               // 符合条件交换{swap(nums[i++], nums[j++]);	// 同时移动}else                            // 不符检测指针单独移动{++i;}}}
};

时间复杂度：O(N)
空间复杂度：O(1)

这里的 “ 指针 ” 是数组下标，使用 交换算法。

保证检测指针位置 >= 交换指针位置：

1. 若数组中没有 0 时，其他数的相对位置交换后也不变。

2. 数组中有 0 时，若交换指针没有检测到 0，检测指针单独前进，两个指针出现距离差，检测到非 0 数交换时检测指针指向的数一定是非 0 数，交换指针指向的数一定是 0，此时交换有效。

这题中有一个细节就是非零元素的相对顺序，不过交换时刚好不会影响。

大小分类

给定一个 int 类型的数组(长度 >= 3)和数组中的任意一个元素 target，请在数组中将小于 target 的元素放在 target 左侧，大于或等于 target 的元素放在 target 右侧。

请注意 ，必须在不开辟额外空间的情况下原地对数组进行操作。

#include <iostream>
#include <vector>
using namespace std;void sizeClassify(vector<int>& arr, int target)
{int i = 0;							// 检测int j = 0;							// 交换int index = 0;						// 定位 targetwhile (i < arr.size()){if (arr[i] == target)			// 为最后交换准备，寻找 target 下标{index = i;}if (arr[i] < target)			// 小于交换，两指针同++{swap(arr[i++], arr[j++]);}else							// 否则检测指针++{++i;}}// i 遍历完 arr, j 刚好在第一个大于等于 target 元素的位置swap(arr[index], arr[j]);			// 交换 index 与 j，保证 左侧小于 target，右侧大于等于 target
}void test1()
{vector<int> arr = { 5, 3, 5, 8, 9, 4, 8, 1, 7, 2, 6, 5, 1, 0, 10 };sizeClassify(arr, 6);for (auto e : arr){cout << e << " ";}cout << endl;
}int main()
{test1();return 0;
}

时间复杂度：O(N)
空间复杂度：O(1)

原理与上题相同，并且这个算法思想可以运用在快速排序中，交换时使用双指针，在通过分治将交换范围不断缩小，继续交换到 数组长度为 1 时停止交换，此时就完成了排序。

覆盖

覆盖指的是双指针两个条件中的算法方面，“ 指针 ” 移动规则未定。

力扣：88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

原题详细信息请参考：力扣：88. 合并两个有序数组

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i = m - 1;int j = n - 1;int last = nums1.size() - 1;while (i >= 0 && j >= 0)            // 第一次放置，谁大放 nums1 的 last 位置{                                   // 并且退出循环时 i 和 j 中必定有一个小于 0，一个大于或等于 0if (nums1[i] > nums2[j])        // nums1[i] 大放 后面{nums1[last--] = nums1[i--]; }else{nums1[last--] = nums2[j--];}}while (i >= 0)                      // 第二次放置，若 i >= 0，说明 nums1 还没有元素放完{                                   // 但是是放在 nums1 数组里的，这步可以省略nums1[last--] = nums1[i--];}while (j >= 0)                      // 若 j >= 0，说明 nums2 还没放完{nums1[last--] = nums2[j--];}}
};

时间复杂度：O(m + n)
空间复杂度：O(1)

这里将 i ，j 分别指向各自数组的最后一个元素，通过对比覆盖原来的位置。

要注意，要从后往前放，不能从前往后放，不然会覆盖原本有效的数据。

实际上，这个思想可以运用在归并排序中，并且能让归并排序保持排序后次序元素相对位置不变，即稳定性这一重要特点。

C语言 memmove 函数实现

memmove 函数是一个拷贝函数，即便原空间和目标空间出现重叠，也可以使用 memmove 函数处理。

详细信息请参考：memmove

#include <cstdio>
#include <cassert>void* my_memmove(void* des, const void* src, size_t num)
{assert(des && src);void* ret = des;if (des > src)										// 要拷贝地址大于被拷贝地址，需要从后向前拷贝{while (num--){*((char*)des + num) = *((char*)src + num);	// 转到 char 类型一字节一字节拷贝}}else												// 否则从前向后拷贝{while (num--){*((char*)des) = *((char*)src);des = (char*)des + 1;						// char* 类型指针 + 1 移动一字节src = (char*)src + 1;}}return ret;											// 返回要拷贝的首元素地址
}void test1()
{int arr1[] = { 1, 2, 3, 4, 5 };my_memmove(arr1, arr1 + 2, sizeof(int) * 3);for (int i = 0; i < 5; ++i){printf("%d ", arr1[i]);}printf("\n");char arr2[] = "hello world";my_memmove(arr2 + 6, arr2, sizeof(char) * 5);for (int i = 0; i < 11; ++i){printf("%c", arr2[i]);}
}int main()
{test1();return 0;
}

时间复杂度：O(N)
空间复杂度：O(1)

这次使用的 “ 指针 ” 是真正的指针了，并且防止覆盖到有效数据，指针的移动规则受限于两个指针的位置影响。

快慢

快慢指的是双指针两个条件中 “ 指针 ” 的移动规则方面，即快慢指针，算法未定。

链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

原题请参考：

力扣：876. 链表的中间结点
牛客网：NC322 链表的中间结点

class Solution {
public:ListNode* middleNode(ListNode* head) {  ListNode* slow = head;ListNode* fast = head;while (fast != nullptr && fast->next != nullptr) // 注意 fast 访问空指针{slow = slow->next;          // 慢指针走一步fast = fast->next->next;    // 快指针走两步}return slow;}
};

时间复杂度：O(N)
空间复杂度：O(1)

可以看到，快慢指针的显著特点是：两个指针中有一个指针比另一个移动的快，并且两者移动的 “ 步伐 ” 是成比例的，上述代码中比例为 2 : 1。

力扣：141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

原题详细信息请参考：力扣：141. 环形链表

class Solution {
public:bool hasCycle(ListNode *head) {     ListNode* slow = head;              // 快慢指针ListNode* fast = head;while (fast != nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;if (fast == slow)               // 相遇为环{return true;}}return false;}
};

时间复杂度：O(N)
空间复杂度：O(1)

关于快慢指针一定会相遇的证明，请参考：(刷题记录3)环形链表与证明

对撞

对撞（相向）指的是双指针两个条件中 “ 指针 ” 的移动规则方面，即对撞指针，算法未定。

力扣：9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数
是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例 1：
输入：x = 121
输出：true

示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

原题请参考：力扣：9. 回文数

class Solution {
public:bool isPalindrome(int x) {string str1(to_string(x));int left = 0;int right = str1.size() - 1;while (left < right)            // 两指针相遇说明遍历完了{if (str1[left++] != str1[right--]){return false;}}return true;}
};

时间复杂度：O(N)
空间复杂度：O(1)

对撞也就是面对面移动，两个指针方向相反，则移动时一段距离后一定会相遇或者背对背移动。

力扣：LCR 139. 训练计划 I

教练使用整数数组 actions 记录一系列核心肌群训练项目编号。为增强训练趣味性，需要将所有奇数编号训练项目调整至偶数编号训练项目之前。请将调整后的训练项目编号以 数组 形式返回。

示例 1：
输入：actions = [1,2,3,4,5]
输出：[1,3,5,2,4]
解释：为正确答案之一

原题请参考：力扣：LCR 139. 训练计划 I

class Solution {
public:vector<int> trainingPlan(vector<int>& actions) {int left = 0;int right = actions.size() - 1;while (left < right)                // 相遇退出{while (left < right && actions[left] % 2 != 0)  // 保证退出时元素为奇数或者left == right {++left;}while (left < right && actions[right] % 2 != 1) // 保证退出时元素为偶数或者left == right{--right;}swap(actions[left], actions[right]);}return actions;}
};

时间复杂度：O(N)
空间复杂度：O(1)

这题也可以用 交换 中的同向（向相同方向移动）指针，不过对撞指针移动上更容易理解。

三、单调性移动规则

我个人给出的单调性移动规则的定义：” 指针 “ 的移动遵循一个移动算法，如果这个算法是单调的，那这个移动规则是具有单调性的，也就是单调性移动规则。

一般情况，双指针两个条件 “ 指针 ” 的移动规则 和 算法 是紧密联系的，甚至仅靠 “ 指针 ” 的移动规则就可以得到结果（例如快慢指针题目部分），因为 移动规则 也是一种算法，根据题目分析刚好它的算法能替代 双指针的算法部分。

这部分我将重点精力放在 ” 指针 “ 的移动规则 上：

二维数组上的移动

牛客网：BC133 回型矩阵

描述：
给你一个整数n，按要求输出n∗n的回型矩阵
输入描述：输入一行，包含一个整数n

1<=n<=19
输出描述：输出n行，每行包含n个正整数.

示例1
输入：
4
输出：
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7

原题请参考：牛客网：BC133 回型矩阵

#include <iostream>
#include <cstring>
using namespace std;int main() 
{int n = 0;cin >> n;int x = 0, y = 0;int i = 2;int arr[n][n];memset(arr, 0, sizeof(int) * n * n);arr[y][x] = 1;while (i <= n * n){while (x + 1 < n && arr[y][x + 1] == 0)     // 向右{arr[y][++x] = i++;}while (y + 1 < n && arr[y + 1][x] == 0)     // 向下{arr[++y][x] = i++;}while (x - 1 >= 0 && arr[y][x - 1] == 0)    // 向左{arr[y][--x] = i++;}while (y - 1 >= 0 && arr[y - 1][x] == 0)    // 向上{arr[--y][x] = i++;}}for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){printf("%d ", arr[i][j]);}printf("\n");}return 0;
}

” 指针 “ 移动遵循右、下、左、上，然后循环继续。

牛客网：BC134 蛇形矩阵

描述：给你一个整数 n，输出 n ∗ n 的蛇形矩阵。
输入描述：输入一行，包含一个整数 n
输出描述：输出 n 行，每行包含 n 个正整数，通过空格分隔。
1<=n<=1000

示例1
输入：
4
输出：
1 2 6 7
3 5 8 13
4 9 12 14
10 11 15 16

原题请参考：牛客网：BC134 蛇形矩阵

#include <iostream>
#include <cstring>
using namespace std;int main() 
{int n = 0;cin >> n;int x = 0;int y = 0;int i = 1;int arr[n][n];memset(arr, 0, sizeof(int) * n * n);arr[y][x] = 1;while (i < n * n){if (x + 1 < n)              // 左{arr[y][++x] = ++i;}while (y + 1 < n && x - 1 >= 0 && arr[y + 1][x - 1] == 0) // 斜向下{arr[++y][--x] = ++i;}if (y + 1 < n)              // 右{arr[++y][x] = ++i;}while (y - 1 >= 0 && x + 1 < n && arr[y - 1][x + 1] == 0) // 斜向上{arr[--y][++x] = ++i;}}for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){printf("%d ", arr[i][j]);}printf("\n");}return 0;
}

与上题同理。

模拟数据结构

用双指针简单模拟数据结构的功能，这种场景通常存在于C语言中。

数据结构的构建在C语言很麻烦，为避免重复造轮子，使用双指针来模拟是一个不错的选择，不过这时的双指针并不是一个独立的算法，移动规则不是单调性的：

破损的键盘

你有一个破损的键盘。键盘上的所有键都可以正常工作，但有时 Home 键或者 End 键会自动按下。你并不知道键盘存在这一问题，而是专心地打稿子，甚至连显示器都没打开。当你打开显示器之后，展现在你面前的是一段悲剧的文本，你的任务是在打开显示器之前计算出这段悲剧文本。

输入包含多组数据。每组数据占一行，包含不超过 100000 个字母、下划线、字符 ” [ “ 或者 " ] “。其中字符 ” [ “ 表示 Home 键，” ] " 表示 End 键。输入结束标志为文件结束符（EOF）。输入文件不超过 5MB。对于每组数据，输出一行，即屏幕上的悲剧文本。

样例输入：
This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University

样例输出：
BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University

原题请参考：《算法竞赛入门经典（第2版）》第 143 页

#include <cstdio>
#include <cstring>const int maxn = 100000 + 5;
int next[maxn];
char s[maxn];void test1()
{while (scanf("%s", s + 1) == 1){int n = strlen(s + 1);int last = 0;					// 模拟 list 的 end()int cur = 0;					// 模拟 list 的 迭代器next[0] = 0;for (int i = 1; i <= n; ++i){char ch = s[i];if (ch == '[')				// 光标移动到头，准备头插{cur = 0;}else if (ch == ']')			// 光标移动到尾，准备尾插{cur = last;}else						// 链表的插入{next[i] = next[cur];	// 修改新节点的指针域next[cur] = i;			// 修改 哨兵/尾/中间 节点的指针域if (cur == last)		// 双指针相等，说明为尾插，将 last 更新{last = i;}cur = i;				// cur 移动到插入字符的位置}}for (int i = next[0]; i != 0; i = next[i])	// 链表的遍历{printf("%c", s[i]);}printf("\n");}
}int main()
{test1();return 0;
}

上述代码来自《算法竞赛入门经典（第2版）》144 页，使用了两个数组 s 和 next，s 表示链表的数据部分， next 表示链表的指针部分。

其中链表的所有节点在 scanf 输入后就全部创建好了，则此时链表插入节点的方式就仅仅是修改指针指向。

我这里写一份 C++ STL 的代码，大家可以对比参考：

#include <iostream>
#include <list>
using namespace std;void test2()
{string s;while (cin >> s){list<char> li;list<char>::iterator it = li.begin();for (int i = 0; i < s.size(); ++i){char ch = s[i];if (ch == '[')					// 光标移动到头，准备头插{it = li.begin();}else if (ch == ']')				// 光标移动到尾，准备尾插{it = li.end();}else							// 链表的插入{it = li.insert(it, ch);		// 插入++it;						// 迭代器 移动到插入字符的下一个位置}}for (auto e : li)					// 链表的遍历{cout << e;}cout << endl;}
}int main()
{test2();return 0;
}