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	字符串相加	[✓]	数学 字符串 模拟	🟢	🀄️ 🔗