Skip to content

Latest commit

 

History

History
15 lines (11 loc) · 1.54 KB

two_pointers.md

File metadata and controls

15 lines (11 loc) · 1.54 KB

Two Pointers

这类题目目前来讲比较容易识别,暂时没有遇到完全想不到这个方法的题目

2021/03/12 来来来,开始打脸上面的话了。 好久没刷题,这两天开始重新操起老本行。现在刷题只做点赞率高的题,基本上这类题都很巧妙,而且不是那种又没啥技术含量代码又臭长,或者说需要知道某个冷门知识点,或者是完全脑筋急转弯的题。 总之这类题做起来收获大,会觉得很巧妙。 今天就做了一道 611. Valid Triangle Number。 猛一看觉得挺简单啊,但是想N^3好像没啥意思。 然后开始觉得可以用two pointers,但是问题来了,如何设定two pointers,我一度想到了用three pointers... 整个过程脑子有点锈,几次在想是不是三指针,但又觉得怎么可能。。。

先排序是肯定的,排序后如何用有序来缩减查找次数,有点卡壳,好久不做题脑子还是锈了啊。 最终还是看了discussion 。。。
果然,思路没问题,问题就出在如何剥离two pointer,总结一下就是右侧最大边,直接iterate一边。 而左侧区间使用two pointer,里面巧妙的地方在于,这个跟二维矩阵查找最值是一个道理(从二维矩阵右上角开始往坐下角查找,充分利用单调性。 可是问题在于这里面是一维数组,不够直观,但是本质是一样的,依然是从左右两边界点做two pointers,往中间压缩搜索。)

但是总感觉这个效率还可以再提升,最外层不需要iterate一遍