Skip to content

Latest commit

 

History

History
52 lines (27 loc) · 3.7 KB

双指针.md

File metadata and controls

52 lines (27 loc) · 3.7 KB

双指针

相关题目

双指针

27. 移除元素

344. 反转字符串

剑指Offer 05.替换空格

151. 翻转字符串里的单词

206. 反转链表

19. 删除链表的倒数第 N 个结点

面试题 02.07. 链表相交

142. 环形链表 II

15. 三数之和

18. 四数之和

11. 盛最多水的容器

42. 接雨水

字符串和数字顺序转换

滑动窗口

209. 长度最小的子数组

904. 水果成篮

3. 无重复字符的最长子串

76. 最小覆盖子串

总结

双指针在字符串、数组、链表等数据结构中常常可以看见。一般分为两种,双指针从首尾两端向中间靠近;或者从同一个方向出发,这种一般也叫快慢指针。在处理双指针的题时,两个指针的初始位置移动条件是解题的关键。如果运用得当,可以将时间复杂度O(n2)的时间复杂度降为O(n)

滑动窗口

滑动窗口主要是通过左右指针形成一个“窗口大小”来求解一些连续子串/子数组/子串能否组成主串等问题。

左右指针一般是从同一个位置开始,根据不同的条件,左右指针移动的时机不同。

根据题目的要求,左右指针的移动时机是解题的关键