3.10 双指针
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 | 字符串相加 | 数学 字符串 模拟 |