JavaScript刷LeetCode拿offer-双指针技巧(上)
创始人
2025-05-28 05:57:55
0

一、前言

一般情况下,遍历数组(或者字符串)操作,都是采用单指针从前往后或者从后往前依次访问数组(或者字符串)中的元素。

而对于以下情况,只采用单指针处理,则会徒增时间复杂度和空间复杂度:

  • 例如:找到两个数使得它们相加之和等于目标数,采用单指针处理,则需要嵌套循环,使得时间复杂度增长为 O(n^2);

  • 再例如:翻转数组,采用单指针处理,则需要额外内存空间,使得空间复杂度增长为 O(n);

利用双指针技巧则可以优化上述解决方案:

  • 第一个例子:可以先对采用数组进行排序预处理,再创建前后指针向中间遍历,遍历的时间复杂度为 O(n),整体时间复杂度主要取决于排序算法,通常为 O(nlogn);

  • 第二个列子:一个指针负责遍历,另外一个指针负责交换元素,从而使得空间复杂度为 O(1);

双指针没有复杂的定义,总结起来主要处理两类问题:

  • 将嵌套循环转化为单循环问题

  • 通过指针记录状态,从而优化空间复杂度

下面的实战分析会让你感受双指针的威力。

二、167. 两数之和 II - 输入有序数组

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

这道题目采用单指针的做法只能通过嵌套循环枚举所有两数之和的方法来解决,时间复杂度为 O(n^2)。

恰巧本题中的数组已经是有序数组,那么直接创建前后指针:

  • 如果两数之后大于 target,尾指针向前移动;

  • 如果两数之和小于 target,头指针向后移动;

在这里插入图片描述

上述代码利用双指针技巧成功地将时间复杂度降低为 O(n)。

三、344. 反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

本题采用单指针的方法,需要创建一个额外的数组来保存翻转后的元素,空间复杂度为 O(n)。

利用双指针技巧,则可以在遍历的过程中同时完成交换元素的操作,时间复杂度降低为 O(1)

在这里插入图片描述

相同类型的题目还有:

  • 【345. 反转字符串中的元音字母】

四、141. 环形链表

给定一个链表,判断链表中是否有环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

在链表这种数据结构中,采用前文所说的前后指针并不一定有效(例如单向链表),这种情况下,双指针的表现形式为:快慢指针

快慢指针指的是:设置两个前进方向相同但速度不同的指针。

本题中,设置每次移动一个单位的慢指针和每次移动两个单位的快指针,那么他们必定会在环内相遇:

在这里插入图片描述

参考视频:传送门

相同类型的题目还有:

  • 【26. 删除排序数组中的重复项】

五、125. 验证回文串

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。说明:本题中,我们将空字符串定义为有效的回文串。

回文字符串问题是双指针的经典应用,同时也是面试题中的常客。

在这里插入图片描述

六、27. 移除元素

给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

显而易见的解决方法是通过 while + splice 处理,但是 splice 操作方法是非常耗时的,每次删除元素之后,需要重排数组中的元素,具有相同副作用的操作方法还有 unshift 和 shift 。 (具体可以查看 V8 源码)

相比较下,pop 和 push 则是非常快的操作方法,这里可以采用双指针 + pop 操作方法,进一步优化时间复杂度:

在这里插入图片描述

写在最后

算法作为计算机的基础学科,用 JavaScript 刷,一点也不丢人ε=ε=ε=┏(゜ロ゜;)┛。

本系列文章会分别给出一种算法的3种难度的总结篇(简单难度,中等难度以及困难难度)。在简单难度中,会介绍该算法的基本知识与实现,另外两个难度,着重讲解解题的思路。

如果本文对您有所帮助,可以点赞或者关注来鼓励博主。

相关内容

热门资讯

疯抢43轮!溢价33.9%!刚... 就在刚刚,江宁两幅低密地块成功出让!其中,三山G50地块热度非常高,该地块是三山板块近10年来首次推...
57岁湖北前首富骤然身亡,家居... wumiancaijing.com / 几个月前才喊着“既没有退休打算,更没想过逃避责任”的汪林朋...
布米普特拉北京投资基金管理有限... 当地时间七月二十九日,美国液化天然气(LNG)出口领域的新锐巨头Venture Global宣布成功...
国泰A500ETF半年蒸发百亿... 2025年中,公募总规模突破34万亿元,同比增加3万亿,其中指数基金的规模净增了2.17万亿元,是主...
原创 美... 前言 近日,美国财政部长贝森特在瑞典斯德哥尔摩的美中贸易谈判中公开透露。 美国国会正在审议一项针对...
年入250亿,波司登让中产又爱... 文 | 本原财经 中产的心头好,“羽绒服之王”波司登交卷了:2025财年,营收首次达到259.02...
创业板指跌逾2%!下跌个股近4... 【大河财立方消息】7月30日午后,指数走弱,创业板指下挫跌逾2.00%,沪指跌0.16%,深成指跌1...
纺织行业上市公司董秘PK:太平... 来源:新浪证券 数据显示,截止7月29日,A股市场共有5817家上市公司。董秘作为连接投资者与上市公...
文远知行Robotaxi获沙特... 本报讯 (记者袁传玺)7月28日,广州文远知行科技有限公司(以下简称“文远知行”,Nasdaq:WR...
新三板创新层公司九州量子大宗交... 每经讯,2025年7月30日,新三板创新层公司九州量子(837638,收盘价:1.64元)发生一笔大...
美国将对欧盟葡萄酒征收15%关... 经过紧张的谈判和不断升级的猜测,美国最终确认对所有进入美国市场的欧盟商品(包括葡萄酒、烈酒和利口酒)...
阿维塔陈卓:拟明年下半年推出与... 凤凰网科技讯 7月30日,阿维塔科技总裁陈卓在中国长安汽车集团有限公司正式成立后首场媒体沟通会上透露...
累计融资5亿! 广州跑出超级独... 对话 | 铅笔道CEO 王方 撰稿 | 铅笔道编辑 赵松格 外卖赛道有美团,生物医药界也有“美团”?...
美国股市今夏是否会过热?专家建... 财联社7月30日讯(编辑 黄君芝)对金融市场来说,今年夏天是一个复杂的时期。尽管市场一直在猜测未来会...
2025“数通链谷”杯上海市区... 7月30日,2025“数通链谷”杯上海市区块链产业应用职工劳动和技能竞赛在上海市静安区市北高新园区数...
李想回忆被赶出公司:站在对方的... 近日,李想在与鲁豫的对话中,回忆人生低谷:2008年,自己曾被创业伙伴联合逼宫,汽车之家面临严重的财...
中证香港300银行指数报118... 金融界7月30日消息,A股三大指数收盘涨跌不一,中证香港300银行指数 (H300银行,H30324...
凯德北京投资基金管理有限公司:... 7月15日,A股上演惊险过山车行情。沪指早盘冲高至3278点后快速回落,最终微涨0.17%报3241...
美财政部长称中国如继续购买俄罗... 7月30日,外交部发言人郭嘉昆主持例行记者会。有记者问:美国财政部长表示,如果中国继续购买俄罗斯石油...