双指针

解法:

就是用两个指针,从两侧逼近就行了

做过的双指针

盛最多水的容器

(20 分钟)
双指针法挺好的,从两边逼近,短的那个去尝试,找到所有的可能的大的

三数之和

(1 个小时)—-中等—–双指针
最开始用的回溯法,被测例搞死了,313 个通过了 311 个,一直超时。
感觉是很多题其实很多解法,for 循环,回溯,多指针,哪个合适其实很难说。回溯法效率不算很高,毕竟是一种全排列算法。
顺便学习下双指针。
双指针逼近算法写了也超时了。

nums.sort((a, b) => a-b);

image.png
这一题双指针简直过分!!取值和遍历分开计算。最大化减少遍历了。

无重复字符的最长子串

(40 分钟)—-中等—–双指针
天啊,就因为多重复了一步,就过不了!!我的算法都对了啊!!
image.png

最接近的三数之和

(40 分钟) —-中等—双指针
先用了 3 层 for 循环,能过就是很惨
image.png
后来改成了双指针,好多了

删除排序数组中的重复项

(5 分钟)—简单—双指针
最简单的用 splice 写,5 分钟很快,不过这一题用双指针也不错的
image.png
看了答案的思想之后,换成双指针答案好像更好了
image.png

移除元素

(2 分钟)—简单—双指针
直接用双指针来做
image.png
题目还是很重要的,说是顺序可以不管,于是第二个指针改成数组 length,每次跟最后的换位置,
image.png
挺有意思的。

反转字符串

(2 分钟)—简单—双指针
image.png

两数之和 II - 输入有序数组

(5 分钟)—简单—双指针
image.png

最大连续 1 的个数

(5 分钟)—简单—双指针
image.png

长度最小的子数组

(20 分钟)—中等—双指针
image.png

长度最小的子数组

(10 分钟)—中等—双指针
比较容易想到的双指针
image.png

接雨水


40 分钟–困难–双指针
这一道直接看了答案,就是左边右边一起逼近,如果出现更高的就统计另一边。左右各维护一个最大值。
image.png


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 981909093@qq.com

文章标题:双指针

文章字数:555

本文作者:泽鹿

发布时间:2019-08-29, 17:25:33

最后更新:2019-09-09, 15:52:23

原始链接:http://panyifei.github.io/2019/08/29/算法/leetcode/双指针/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏