常见于Leetcode简单和中等题,在特定的题目背景和要求下可能成为困难题。
如果是滑动窗口,则难度基本处在中等和困难的段位。
简述
双指针是大多数算法初学者在进阶路上遇到的第一个可以靠自己想出来的中阶算法。
在面对数组中的局部搜索问题(即找一段符合条件的arr[i:j])时,相比于O(N^2)的暴力破解,在特定的要求下,算法初学者会开始思考:有没有一种办法可以在只搜索一遍数组的情况下,就把问题解决。
一番酣畅淋漓的思考过后,初学者会意识到,相比于暴力破解的无脑移动 i和j 两个搜索指针,完全可以通过自定义指针的移动规则,来记录更有意义的内容,从而忽略一些不必要的重复搜索,实现O(N)的时间复杂度。
也正是在这时,大多数初学者也开始意识到: 空间换时间 的含义。
当然,双指针,是一种很笼统,很粗糙的称呼,任何使用了两个有特定移动规则的指针的算法,都可以称为双指针。因此二分法也算是双指针算法,只不过二分法这个算法的精髓还是在于bisection的核心思想。
双指针的类型
根据两个指针的移动规则,可以将双指针算法分为以下四种:
- 左右指针 / 首尾指针 / 对撞指针 特点:初始化时,两个指针分别指向数组的头和尾,两者不断向中间逼近,直到两指针相遇为止。
- 快慢指针 特点:两个指针都从数组一端出发,两个指针的移动规则有明显的速度差别,导致一个指针移动的特别快,一个移动的特别慢。
- 平行指针 特点:两个指针分布于不同的数组,大多数情况下,两个指针的移动策略是相同的。
- 滑动窗口 特点:两个指针从数组一端出发,但是两个指针始终保持一定的距离
常用于:有序数组中的搜索 (e.g. 二分法)
【代码参照 二分法】
常用于:链表(找中点,找环)
常用于: 同时搜索多个数组/链表 以及 两个有序子数组合并(并归排序)
这个距离大多数情况下是固定值,但如果题目求解的就是这个距离的极值,那就可能是变化的
常用于:子数组、字符串和子字符串问题
双指针的难点⭐️
难点普遍只有两个,分别对应设计和实现:
- 设计:是否可以明确定义两个指针分别的移动策略 (两个指针分别是干啥的)
- 实现:是否可以在coding的过程中考虑到所有的边缘情况(写不写得出来)
通常是因为缺乏足够的练习,导致想不到可以用双指针算法【这是最不应该的】,或者想不通两个指针的移动逻辑,导致解题失败。 因此,针对难点一,除了多练没有别的技巧。
难点二则是缺乏足够的代码功底,在处理复杂的逻辑时会失去耐心或者疏漏。与难点一不同,这个是可以通过技巧弥补的。
技巧:「循环不变量」
循环不变量,指的是我们在编写代码的时候,要一只遵循不变的一个性质。这个性质需要我们根据问题自己定义, ,一定要确保「初始化」「循环遍历」「结束」这三个阶段相同的性质,使得一个问题能够被正确解决。
区间不同的定义决定了不同的初始化逻辑、遍历过程中的逻辑。
因此,循环不变量并不是所谓双指针算法的精髓,而是针对复杂的题型,想要把双指针解法写得足够周密的技巧。
这个技巧也同样适用于其他的算法。双指针基础问题经典合集
| 编号 | 名称 | 难度 | 双指针解法 |
|---|---|---|---|
| 26 | 删除有序数组汇总的重复项 | 简单 |
双指针类型:快慢指针 快指针: 不断去寻找下一个未知元素 |
| 674 | 最长连续递增序列 | 简单 |
双指针类型:快慢指针 快指针:不断去寻找下一个满足单调递增的元素 当快指针元素违背单调递增时,慢指针移动到当前快指针的位置,意味着搜索新的递增序列 |
| 977 | 有序数组的平方 | 简单 |
双指针类型:对撞指针 左指针:表示负数一端可能竞争平方后最大值的元素 hint: 当能排除存在负数、正数的情况下可以直接出结果 |
| 27 | 移除元素 | 简单 |
双指针类型:快慢指针 快指针:不断去寻找下一个不需要移除的元素 |
| 80 | 删除排序数组中的重复项 II | 中等 |
双指针类型:快慢指针 快指针:不断去寻找下一个元素,并根据重复次数决定是否插入和是否更新对照元素 |
| 283 | 移动零 | 简单 |
双指针类型:快慢指针 快指针:不断去寻找下一个非零元素 |
| 11 | 盛最多水的容器 | 中等 |
双指针类型:对撞指针 左指针:指向当前遍历层的左边界 |
双指针循环不变量问题合集
| 编号 | 名称 | 难度 | 双指针解法 |
|---|---|---|---|
| 75 | 颜色分类 | 中等 |
【荷兰国旗问题⭐️】 双指针类型:对撞指针【变种】
快指针: 定位交换1的位置 存在右指针和i同时都是2的情况,因此需要使用while i <= right and nums[i] == 2: … right -= 1的方式来确保不会漏掉左边的2。【默认i是从0到n-1的话】 |
| 215 | 数组中的第K个最大元素 | 中等 |
【快速排序的变种】 双指针类型:对撞指针【变种】 左右指针不严格区分,配合哨兵划分和递归来进行基准值左右的划分,直至终止。 技巧:快速选择题目要求的是找到第K大的值,因此并不需要排序正个数组,而是类似于【二分搜索】,当通过pivot左右两边的数量,可以判断出第K大的必不存在于一个区间时,可以直接舍弃该区间。 因为时间复杂度要求O(N),明显是一个分治算法。 |
| 59 | 螺旋矩阵II | 中等 |
【基于循环不变量的模拟法】 循环不变量:按层模拟,每一层四条边,每一条边的区间分别是:【左,右),【上,下),【右,左),【下,上)。 直到遍历所有层。 |
双指针链表问题合集
| 编号 | 名称 | 难度 | 双指针解法 |
|---|---|---|---|
| 141 | 环形链表 | 简单 |
双指针类型:快慢指针 快指针: 一次走两个 |
| 19 | 删除链表的倒数第N个节点 | 中等 |
双指针类型:快慢指针 快指针: 领先慢指针N个节点 快指针到头了,直接移除慢指针指向的下一个节点 |
| 876 | 链表的中间节点 | 简单 |
双指针类型:快慢指针 快指针: 一次走两个节点 |
| 142 | 环形链表II | 中等 |
双指针类型:快慢指针 快指针: 一次走两个节点 需要运用一些数学的思维, 假设进环之前要走a个节点,环中有b个节点,会发现: 快慢指针相遇时,快指针走了慢指针两倍的步数,而最终两者相遇,可以获得以下关系:
两者做减法,去除重复的区域,则可以证明出
而此时需要再次构快慢指针,将慢指针回到head,用相同的步幅出发,相遇时则正好指向环的入口。 |
| 160 | 相交链表 | 简单 |
【这题不要求空间复杂度,可以用哈希表做,所以是简单题,但是双指针可以O(1)空间,O(m+n)时间,这一步难一点,算是中等难度】 双指针类型:两个单指针 技巧:其实核心的技巧是将两个链表对齐,可以通过遍历求长度,然后根据长度将两者对齐,然后两个链表都给从头用一个指针同步遍历,什么时候遍历到同一个节点,就是相交入口。 |
双指针优化去重问题合集
这一类题型通常解法不唯一,但是往往简化求解过程的算法都会导致去重过程更加复杂,可以通过排序后的双指针简化去重复杂度。
双指针法将时间复杂度: O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级
| 编号 | 名称 | 难度 | 双指针解法 |
|---|---|---|---|
| 15 | 三数之和 | 中等 |
【哈希解法】
在Leetcode门神: 两数之和的基础上,人们第一个想到的解法肯定是哈希, 两层for循环就可以确定 a 和b 的数值了, 可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过,其实这个思路是正确的,但是我们有一个非常棘手的问题,就是题目中说的不可以包含重复的三元组 先通过哈希找到所有索引上不重复的三元组再去重是非常费时的,很容易超时 这道题目使用双指针法 要比哈希法高效一些基于这种问题的复杂度,我们要使用的双指针类型也比较特殊,我称之为: 循环对撞指针 首先将数组排序,然后有一层for循环,i从下标0的地方开始,同时定一个下标left 定义在i+1的位置上,定义下标right 在数组结尾的位置上 指针移动策略如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了,因为数组是排序后了,所以right下标就应该向左移动,这样才能让三数之和小一些。 如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了,left 就向右移动,才能让三数之和大一些,直到left与right相遇为止。 |
| 18 | 四数之和 | 中等 |
和15.三数之和 是一个思路，都是使用双指针法, 基本解法就是在15.三数之和 的基础上再套一层for循环。 四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值,依然是循环内有left和right下标作为双指针, 找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况,三数之和的时间复杂度是O(n^2),四数之和的时间复杂度是O(n^3) 。 那么一样的道理，五数之和、六数之和等等都采用这种解法 |
思考: 两数之和 可不可以用双指针简化?
答案是不行。道理很简单,因为二数之和最后要求的返回值是索引,因此排序会打乱原有顺序,原有索引就失效了。 而不排序的话,双指针无法简化去重,所以无法用双指针求解。
注: 通过Leetcode这些题目的【相似题目】功能,可以获得更多双指针练习题。