3.10 双指针

定义

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

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

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

对撞指针

快慢指针

分离双指针

相关题目

数组双指针

• 对撞指针

题号	标题	题解	标签	难度
0167	两数之和 II - 输入有序数组	JS	数组 双指针 二分查找
0344	反转字符串	JS	双指针 字符串
0345	反转字符串中的元音字母	JS	双指针 字符串
0125	验证回文串	JS	双指针 字符串
0011	盛最多水的容器	JS	贪心 数组 双指针
0611	有效三角形的个数	JS	贪心 数组 双指针 2+
0015	三数之和	JS	数组 双指针 排序
0016	最接近的三数之和	JS	数组 双指针 排序
0018	四数之和	JS	数组 双指针 排序
0259	较小的三数之和	JS	数组 双指针 二分查找 1+
0658	找到 K 个最接近的元素		数组 双指针 二分查找 3+
1099	小于 K 的两数之和		数组 双指针 二分查找 1+
0075	颜色分类		数组 双指针 排序
0360	有序转化数组		数组 数学 双指针 1+
0977	有序数组的平方		数组 双指针 排序
0881	救生艇		贪心 数组 双指针 1+
0042	接雨水	JS	栈 数组 双指针 2+
0443	压缩字符串		双指针 字符串

• 快慢指针

题号	标题	题解	标签	难度
0026	删除有序数组中的重复项	JS	数组 双指针
0080	删除有序数组中的重复项 II	JS	数组 双指针
0027	移除元素	JS	数组 双指针
0283	移动零	JS	数组 双指针
0845	数组中的最长山脉		数组 双指针 动态规划 1+
0088	合并两个有序数组	JS	数组 双指针 排序
0719	找出第 K 小的数对距离		数组 双指针 二分查找 1+
0334	递增的三元子序列		贪心 数组
0978	最长湍流子数组		数组 动态规划 滑动窗口
剑指 Offer 21	调整数组顺序使奇数位于偶数前面	JS	数组 双指针 排序

• 分离双指针

题号	标题	题解	标签	难度
0350	两个数组的交集 II		数组 哈希表 双指针 2+
0925	长按键入		双指针 字符串
0844	比较含退格的字符串	JS	栈 双指针 字符串 1+
1229	安排会议日程		数组 双指针 排序
0415	字符串相加		数学 字符串 模拟