::: info 定义 双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。 :::
- 如果两个指针方向相反，则称为「对撞指针」；
- 如果两个指针方向相同，则称为「快慢指针」；
- 如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。
在数组的区间问题上，暴力算法的时间复杂度往往是 O(n^2)。而双指针利用了区间「单调性」的性质，可以将时间复杂度降到 O(n)。
- 对撞指针
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 167 | 两数之和 II - 输入有序数组 | [✓] | 数组 双指针 二分查找 |
Medium |
| 344 | 反转字符串 | [✓] | 双指针 字符串 |
Easy |
| 345 | 反转字符串中的元音字母 | [✓] | 双指针 字符串 |
Easy |
| 125 | 验证回文串 | [✓] | 双指针 字符串 |
Easy |
| 11 | 盛最多水的容器 | [✓] | 贪心 数组 双指针 |
Medium |
| 611 | 有效三角形的个数 | [✓] | 贪心 数组 双指针 2+ |
Medium |
| 15 | 三数之和 | [✓] | 数组 双指针 排序 |
Medium |
| 16 | 最接近的三数之和 | [✓] | 数组 双指针 排序 |
Medium |
| 18 | 四数之和 | [✓] | 数组 双指针 排序 |
Medium |
| 259 | 较小的三数之和 🔒 | [✓] | 数组 双指针 二分查找 1+ |
Medium |
| 658 | 找到 K 个最接近的元素 | 数组 双指针 二分查找 3+ |
Medium | |
| 1099 | 小于 K 的两数之和 🔒 | 数组 双指针 二分查找 1+ |
Easy | |
| 75 | 颜色分类 | [✓] | 数组 双指针 排序 |
Medium |
| 360 | 有序转化数组 🔒 | 数组 数学 双指针 1+ |
Medium | |
| 977 | 有序数组的平方 | 数组 双指针 排序 |
Easy | |
| 881 | 救生艇 | 贪心 数组 双指针 1+ |
Medium | |
| 42 | 接雨水 | [✓] | 栈 数组 双指针 2+ |
Hard |
| 443 | 压缩字符串 | [✓] | 双指针 字符串 |
Medium |
- 快慢指针
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 26 | 删除有序数组中的重复项 | [✓] | 数组 双指针 |
Easy |
| 80 | 删除有序数组中的重复项 II | [✓] | 数组 双指针 |
Medium |
| 27 | 移除元素 | [✓] | 数组 双指针 |
Easy |
| 283 | 移动零 | [✓] | 数组 双指针 |
Easy |
| 845 | 数组中的最长山脉 | [✓] | 数组 双指针 动态规划 1+ |
Medium |
| 88 | 合并两个有序数组 | [✓] | 数组 双指针 排序 |
Easy |
| 719 | 找出第 K 小的数对距离 | 数组 双指针 二分查找 1+ |
Hard | |
| 334 | 递增的三元子序列 | [✓] | 贪心 数组 |
Medium |
| 978 | 最长湍流子数组 | 数组 动态规划 滑动窗口 |
Medium | |
| 剑指 Offer 21 | 调整数组顺序使奇数位于偶数前面 | [✓] | 数组 双指针 排序 |
Easy |
- 分离双指针
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 350 | 两个数组的交集 II | 数组 哈希表 双指针 2+ |
Easy | |
| 925 | 长按键入 | 双指针 字符串 |
Easy | |
| 844 | 比较含退格的字符串 | [✓] | 栈 双指针 字符串 1+ |
Easy |
| 1229 | 安排会议日程 🔒 | 数组 双指针 排序 |
Medium | |
| 415 | 字符串相加 | [✓] | 数学 字符串 模拟 |
Easy |