概述

image.png

举例

普通双指针

a 为一数组 {4,1,5,7,9} 求其中两数，两数和为12，且两数不相等。
image.png 定义如图双指针，j 一直向后遍历，到末尾并未找到
image.png i 和 j 同时右移，j 再次向后遍历
以此类推直至 找到 或者 所有可能遍历完未找到
时间复杂度为：O(n^2)

对撞双指针

a 为一有序数组 {1,4,5,7,9} 求其中两数，两数和为12，且两数不相等。
image.png 定义如图首尾双指针
image.png
image.png
image.png
时间复杂度为：O(n)

快慢双指针

判断所给链表是否为环形链表
image.png 定义快慢双指针初始位置相同，s 为慢指针，f 为快指针
s 和 f 同时移动，发现某一时刻 s 和 f 相遇，则该链表即为环形链表

LeetCode练习

#141

#881