two指针

admin 2022年1月6日01:36:03安全博客评论14 views481字阅读1分36秒阅读模式

概念

双指针,顾名思义,就是利用两个指针去遍历数组,一般来说,遍历数组采用的是单指针(index)去遍历,两个指针一般是在有序数组中使用,一个放首,一个放尾,同时向中间遍历,直到两个指针相交,完成遍历,时间复杂度也是O(n)。

使用场景

  • 时间复杂度:O(n) 并且 One Pass
  • 空间要求:in place
  • 两数之和满足某条件
    • 先对数组排序,再采用两个指针,分别从前和后往中间遍历,front增大,tail减小,通过对条件的判断,可以在O(n)内遍历,而非使用双重循环。
  • in place交换
    • 一个指针正常遍历,另一个指针去找可以用来交换的元素。

例题

  1. 有序数组的 Two Sum
  2. 两数平方和
  3. 反转字符串中的元音字符
  4. 回文字符串
  5. 归并两个有序数组
  6. 判断链表是否存在环
  7. 最长子序列

https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8F%8C%E6%8C%87%E9%92%88.md

参考文章:

算法之双指针

FROM :blog.cfyqy.com | Author:cfyqy

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:36:03
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  two指针 http://cn-sec.com/archives/721953.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: