双指针技巧入门
双指针技巧套路框架
双指针技巧分为两类,一类是“快、慢指针”,一类是“左、右指针”。前者主要解决链表中的问题,比如典型的判定链表中是否包含环;后者主要解决数组(或者字符串)中的问题,比如二分搜索。
快、慢指针的常用算法
1.判定链表中是否有环?设置快、慢指针解决。
solution:
1 | boolean hasCycle(ListNode head){ |
2.已知链表中含有环,返回这个环的起始位置
solution:
1 | ListNode detectCycle(ListNode head){ |
可以看到,当快、慢指针相遇时,让其中任何一个指针只像头节点,然后让两个指针以相同的速度前进,再次相遇时所在的节点位置就是环开始的位置。//数学逻辑推理
3.寻找无环单链表的中点
solution:
1 | while(fast != null && fast.next != null){ |
注:当链表长度是奇数时,slow
恰巧停在中点位置;当链表的长度是偶数时,slow
最终的位置是中间偏右。
4.寻找单链表的倒数第k个元素
solution:
1 | ListNode slow, fast; |
快指针先走k步,然后慢指针、快指针一起走,直到快指针走到头了,慢指针就走到倒数第k个元素了。
左、右指针的常用算法
左、右指针一般运用在数组问题中,一般初始化为left = 0, right = len(nums) - 1
。
1.二分搜索(略,见下一小节)
2.两数之和(略)
3.反转数组(略)
4.滑动窗口算法(略,见下下小节)
tips:一般数组有序就可以考虑左、右双指针。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ae86's Blog!