3.10 双指针

定义

双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。

• 如果两个指针方向相反，则称为「对撞指针」；
• 如果两个指针方向相同，则称为「快慢指针」；
• 如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。

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

对撞指针

快慢指针

分离双指针

相关题目

数组双指针

• 对撞指针

题号	标题	题解	标签	难度
167	两数之和 II - 输入有序数组	[✓]	数组 双指针 二分查找
344	反转字符串	[✓]	双指针 字符串
345	反转字符串中的元音字母	[✓]	双指针 字符串
125	验证回文串	[✓]	双指针 字符串
11	盛最多水的容器	[✓]	贪心 数组 双指针
611	有效三角形的个数	[✓]	贪心 数组 双指针 2+
15	三数之和	[✓]	数组 双指针 排序
16	最接近的三数之和	[✓]	数组 双指针 排序
18	四数之和	[✓]	数组 双指针 排序
259	较小的三数之和 🔒	[✓]	数组 双指针 二分查找 1+
658	找到 K 个最接近的元素		数组 双指针 二分查找 3+
1099	小于 K 的两数之和 🔒		数组 双指针 二分查找 1+
75	颜色分类	[✓]	数组 双指针 排序
360	有序转化数组 🔒		数组 数学 双指针 1+
977	有序数组的平方		数组 双指针 排序
881	救生艇		贪心 数组 双指针 1+
42	接雨水	[✓]	栈 数组 双指针 2+
443	压缩字符串	[✓]	双指针 字符串

• 快慢指针

题号	标题	题解	标签	难度
26	删除有序数组中的重复项	[✓]	数组 双指针
80	删除有序数组中的重复项 II	[✓]	数组 双指针
27	移除元素	[✓]	数组 双指针
283	移动零	[✓]	数组 双指针
845	数组中的最长山脉	[✓]	数组 双指针 动态规划 1+
88	合并两个有序数组	[✓]	数组 双指针 排序
719	找出第 K 小的数对距离		数组 双指针 二分查找 1+
334	递增的三元子序列	[✓]	贪心 数组
978	最长湍流子数组		数组 动态规划 滑动窗口
剑指 Offer 21	调整数组顺序使奇数位于偶数前面	[✓]	数组 双指针 排序

• 分离双指针

题号	标题	题解	标签	难度
350	两个数组的交集 II		数组 哈希表 双指针 2+
925	长按键入		双指针 字符串
844	比较含退格的字符串	[✓]	栈 双指针 字符串 1+
1229	安排会议日程 🔒		数组 双指针 排序
415	字符串相加	[✓]	数学 字符串 模拟