跳至主要內容

3.10 双指针


3.10 双指针

定义

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

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

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

对撞指针

快慢指针

分离双指针

相关题目

数组双指针

  • 对撞指针
题号标题题解标签难度力扣
167两数之和 II - 输入有序数组[✓]数组 双指针 二分查找🟠🀄️open in new window 🔗open in new window
344反转字符串[✓]双指针 字符串🟢🀄️open in new window 🔗open in new window
345反转字符串中的元音字母[✓]双指针 字符串🟢🀄️open in new window 🔗open in new window
125验证回文串[✓]双指针 字符串🟢🀄️open in new window 🔗open in new window
11盛最多水的容器[✓]贪心 数组 双指针🟠🀄️open in new window 🔗open in new window
611有效三角形的个数[✓]贪心 数组 双指针 2+🟠🀄️open in new window 🔗open in new window
15三数之和[✓]数组 双指针 排序🟠🀄️open in new window 🔗open in new window
16最接近的三数之和[✓]数组 双指针 排序🟠🀄️open in new window 🔗open in new window
18四数之和[✓]数组 双指针 排序🟠🀄️open in new window 🔗open in new window
259较小的三数之和 🔒[✓]数组 双指针 二分查找 1+🟠🀄️open in new window 🔗open in new window
658找到 K 个最接近的元素数组 双指针 二分查找 3+🟠🀄️open in new window 🔗open in new window
1099小于 K 的两数之和 🔒数组 双指针 二分查找 1+🟢🀄️open in new window 🔗open in new window
75颜色分类[✓]数组 双指针 排序🟠🀄️open in new window 🔗open in new window
360有序转化数组 🔒数组 数学 双指针 1+🟠🀄️open in new window 🔗open in new window
977有序数组的平方数组 双指针 排序🟢🀄️open in new window 🔗open in new window
881救生艇贪心 数组 双指针 1+🟠🀄️open in new window 🔗open in new window
42接雨水[✓] 数组 双指针 2+🔴🀄️open in new window 🔗open in new window
443压缩字符串[✓]双指针 字符串🟠🀄️open in new window 🔗open in new window
  • 快慢指针
题号标题题解标签难度力扣
26删除有序数组中的重复项[✓]数组 双指针🟢🀄️open in new window 🔗open in new window
80删除有序数组中的重复项 II[✓]数组 双指针🟠🀄️open in new window 🔗open in new window
27移除元素[✓]数组 双指针🟢🀄️open in new window 🔗open in new window
283移动零[✓]数组 双指针🟢🀄️open in new window 🔗open in new window
845数组中的最长山脉[✓]数组 双指针 动态规划 1+🟠🀄️open in new window 🔗open in new window
88合并两个有序数组[✓]数组 双指针 排序🟢🀄️open in new window 🔗open in new window
719找出第 K 小的数对距离数组 双指针 二分查找 1+🔴🀄️open in new window 🔗open in new window
334递增的三元子序列[✓]贪心 数组🟠🀄️open in new window 🔗open in new window
978最长湍流子数组数组 动态规划 滑动窗口🟠🀄️open in new window 🔗open in new window
剑指 Offer 21调整数组顺序使奇数位于偶数前面[✓]数组 双指针 排序🟢🀄️open in new window
  • 分离双指针
题号标题题解标签难度力扣
350两个数组的交集 II数组 哈希表 双指针 2+🟢🀄️open in new window 🔗open in new window
925长按键入双指针 字符串🟢🀄️open in new window 🔗open in new window
844比较含退格的字符串[✓] 双指针 字符串 1+🟢🀄️open in new window 🔗open in new window
1229安排会议日程 🔒数组 双指针 排序🟠🀄️open in new window 🔗open in new window
415字符串相加[✓]数学 字符串 模拟🟢🀄️open in new window 🔗open in new window